最小（不重）路径覆盖

给定一个 DAG，求把 DAG 划分为若干条路径，使得每个点都恰好某个路径上的方案中，路径条数最小是多少。

考虑初始化为 nn 条路径，每个路径就是一个单点。然后如果有一条边 (u,v)(u,v)，就可以合并一条以 uu 为结尾的路径和以 vv 为开头的路径。最后答案就是 n−合并次数n-\text{合并次数}。

考虑如何刻画这样的合并过程，我们发现，每个点作为开头和作为结尾都至多被合并一次，那么我们就把每个点拆成两个，(u,u′)(u,u')，uu 和 ss 连接，u′u' 和 tt 连接，用边 (u,v)(u,v) 连接就对应了一条增广路 s−u−v′−ts - u - v' - t，这样正好表示了 uu 作为结尾被合并了一次，vv 作为开头被合并了一次，所以所有边权设置为 11 就能刻画出每个点最多被合并一次的限制。

至于输出方案，也是简单的，一个点是链的开头，就说明它没有作为开头被合并过，也就是它的第二个点到 tt 的边没有流量，判断之后 dfs 找下一个点是什么就能够造出方案。

P2764 最小路径覆盖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct Dinic{
    #define Maxn 500
    #define Maxm 15000
    int tot = 1;
    int hea[Maxn], nex[Maxm<<1], ver[Maxm<<1];
    int tmphea[Maxn], dep[Maxn];
    ll edg[Maxm<<1], sum;
    inline void init()
        { tot = 1, memset(hea, 0 ,sizeof(hea));}
    inline int add_edge(int x,int y,int d){    
        ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
        ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
        return tot - 1;
    }
    inline bool bfs(int s,int t){
        memset(dep, 0, sizeof(dep)), dep[s]=1;
        memcpy(tmphea, hea, sizeof(hea));
        queue<int> q; q.push(s);
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(cur==t)return true;
            for(int i=hea[cur];i;i=nex[i])
                if(edg[i]>0&&!dep[ver[i]])dep[ver[i]]=dep[cur]+1, q.push(ver[i]);
        }
        return false;
    }
    ll dfs(int x,ll flow,int t){
        if(x==t || !flow)return flow;
        ll rest = flow, tmp;
        for(int i=tmphea[x];i&&rest;i=nex[i]){
            tmphea[x]=i;
            if(dep[ver[i]]==dep[x]+1 && edg[i]>0){
                if(!(tmp=dfs(ver[i],min(edg[i], rest),t)))dep[ver[i]]=0;
                edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
            }
        }
        return flow-rest;
    }
    inline ll solve(int s,int t){
        sum = 0;
        while(bfs(s,t))sum+=dfs(s,inf,t);
        return sum;
    }
    #undef Maxn
    #undef Maxm
}G;

int n,m;
const int N = 200;
bool vis[N];
void dfs(int u){
    cout << u << ' ';

    // u 到 v 有一条边，也就是说 u 到 v 的边有流
    for(int i=G.hea[u];i;i=G.nex[i]){
        if(G.ver[i] <=n || G.ver[i] > n*2)continue;
        if(!G.edg[i])dfs(G.ver[i]-n);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    int s=0, t=n*2+1;

    vector<int> es(n+1),et(n+1);

    for(int i=1;i<=n;i++){
        es[i]=G.add_edge(s, i, 1);
        et[i]=G.add_edge(i+n, t, 1);
    }
    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        G.add_edge(u, v+n, 1);
    }
    
    int ans = n - G.solve(s,t);
    for(int i=1;i<=n;i++){
        if(G.edg[et[i]]){
            dfs(i);
            cout << '\n';
        }
    }

    cout << ans << '\n'; 
    return 0;
}

最长反链长度

P10938 Vani和Cl2捉迷藏

给定一个 DAG，求最长反链长度。

反链的定义是：若干个点，使得它们之间不存在一个路径。

最大权闭合子图

考虑把一个点拆成两个 u,u′u,u'，其中 uu 的权值为 −1-1，u′u' 的权值为 11，以及需要建立 (u,u′)(u,u') 之间的边。

然后对于每一条原图上的边 (u,v)(u,v)，在新图上建立 (u′,v)(u', v)。

然后考察这个新图的最大权闭合子图，我们断言它等于反链长度。

考察最长反链的所有开头位置，如果选择了这些开头位置所对应的 u′u' 在闭合子图中，那么从它们开始能到达的节点的贡献会全部被抵消（也就是因为 uu 和 u′u' 都被选择了），此时权值恰好就是最长反链的节点数。

而每个最大权闭合子图一定不会从 uu 开始（因为从 u′u' 开始更好），所以每个最大权闭合子图又至少对应了一个该权值的反链划分，所以这个命题是成立的。

构造方案：uu 在反链中   ⟺  \iff uu 在 TT 里面且 u′u' 在 SS 里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct Dinic{
    #define Maxn 500
    #define Maxm 100000
    int tot = 1;
    int hea[Maxn], nex[Maxm<<1], ver[Maxm<<1];
    int tmphea[Maxn], dep[Maxn];
    ll edg[Maxm<<1], sum;
    inline void init()
        { tot = 1, memset(hea, 0 ,sizeof(hea));}
    inline void add_edge(int x,int y,int d){    
        ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
        ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
    }
    inline bool bfs(int s,int t){
        memset(dep, 0, sizeof(dep)), dep[s]=1;
        memcpy(tmphea, hea, sizeof(hea));
        queue<int> q; q.push(s);
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(cur==t)return true;
            for(int i=hea[cur];i;i=nex[i])
                if(edg[i]>0&&!dep[ver[i]])dep[ver[i]]=dep[cur]+1, q.push(ver[i]);
        }
        return false;
    }
    ll dfs(int x,ll flow,int t){
        if(x==t || !flow)return flow;
        ll rest = flow, tmp;
        for(int i=tmphea[x];i&&rest;i=nex[i]){
            tmphea[x]=i;
            if(dep[ver[i]]==dep[x]+1 && edg[i]>0){
                if(!(tmp=dfs(ver[i],min(edg[i], rest),t)))dep[ver[i]]=0;
                edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
            }
        }
        return flow-rest;
    }
    inline ll solve(int s,int t){
        sum = 0;
        while(bfs(s,t))sum+=dfs(s,inf,t);
        return sum;
    }
    #undef Maxn
    #undef Maxm
}G;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;
    int s=0, t=n*2+1;

    for(int i=1;i<=n;i++){
        G.add_edge(s, i+n, 1);
        G.add_edge(i, t ,1);
        G.add_edge(i, i+n, 1e9);
    }

    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        G.add_edge(u+n, v, 1e9);
    }

    cout << n - G.solve(s, t) << '\n';
    return 0;
}

Dilworth 定理

根据 Dilworth 定理，最长反链长度等于最小链划分（注意，链的定义是一条路径的一个子集）。

不难发现，最小链划分等价于最小点可重复的路径覆盖，而点可重复的路径覆盖可以对原图先求一次传递闭包（也就是构建一张新图 G′G'，u,vu,v 之间有边当前仅当原图存在从 uu 到 vv 的路径），然后 G′G' 的最小（不重）路径覆盖就是原图的可重复最小路径覆盖。

于是就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct Dinic{
    #define Maxn 500
    #define Maxm 100000
    int tot = 1;
    int hea[Maxn], nex[Maxm<<1], ver[Maxm<<1];
    int tmphea[Maxn], dep[Maxn];
    ll edg[Maxm<<1], sum;
    inline void init()
        { tot = 1, memset(hea, 0 ,sizeof(hea));}
    inline void add_edge(int x,int y,int d){    
        ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
        ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
    }
    inline bool bfs(int s,int t){
        memset(dep, 0, sizeof(dep)), dep[s]=1;
        memcpy(tmphea, hea, sizeof(hea));
        queue<int> q; q.push(s);
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(cur==t)return true;
            for(int i=hea[cur];i;i=nex[i])
                if(edg[i]>0&&!dep[ver[i]])dep[ver[i]]=dep[cur]+1, q.push(ver[i]);
        }
        return false;
    }
    ll dfs(int x,ll flow,int t){
        if(x==t || !flow)return flow;
        ll rest = flow, tmp;
        for(int i=tmphea[x];i&&rest;i=nex[i]){
            tmphea[x]=i;
            if(dep[ver[i]]==dep[x]+1 && edg[i]>0){
                if(!(tmp=dfs(ver[i],min(edg[i], rest),t)))dep[ver[i]]=0;
                edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
            }
        }
        return flow-rest;
    }
    inline ll solve(int s,int t){
        sum = 0;
        while(bfs(s,t))sum+=dfs(s,inf,t);
        return sum;
    }
    #undef Maxn
    #undef Maxm
}G;

const int N = 205;
bool d[N][N];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;
    int s=0, t=n*2+1;

    for(int i=1;i<=n;i++){
        G.add_edge(s, i, 1);
        G.add_edge(i+n, t ,1);
    }

    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        d[u][v] = 1;
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][k] && d[k][j])d[i][j]=1;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(d[i][j]){
                G.add_edge(i, j+n, 1);
            }
        }
    }

    cout << n - G.solve(s, t) << '\n';
    return 0;
}

练习

P4298 [CTSC2008] 祭祀

给定一张图，求出一组反链的可行解，和可能在反链中的节点。

用之前说到的最大闭合子图，构造一组可行解是简单的。

我们考虑求出每个点是否可能在反链中。也就是问是否存在一个最小割，使得 uu 在 TT 中，且 u′u' 在 SS 中。

对残余网络先缩点，然后缩点之后得到 DAG 的任何一个大小为 00 的割都是最小割。

那么问题就很简单了，我们希望把 uu 所在的 SCC 划分给 TT，u′u' 所在的 SCC 划分给 SS。

所以，这个点不可能在反链中当且仅当以下三个中某一个成立（显然，u′u' 的 SCC 不可能指向 uu，否则两个点会在同一个 SCC 内）：

  • uu 和 u′u' 在同一个 SCC 之内
  • uu 和 SS 在一个 SCC 之内
  • u′u' 和 TT 在一个 SCC 之内

于是就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct Dinic{
    #define Maxn 500
    #define Maxm 100000
    int tot = 1;
    int hea[Maxn], nex[Maxm<<1], ver[Maxm<<1];
    int tmphea[Maxn], dep[Maxn];
    ll edg[Maxm<<1], sum;
    inline void init()
        { tot = 1, memset(hea, 0 ,sizeof(hea));}
    inline int add_edge(int x,int y,int d){    
        ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
        ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
        return tot-1;
    }
    inline bool bfs(int s,int t){
        memset(dep, 0, sizeof(dep)), dep[s]=1;
        memcpy(tmphea, hea, sizeof(hea));
        queue<int> q; q.push(s);
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(cur==t)return true;
            for(int i=hea[cur];i;i=nex[i])
                if(edg[i]>0&&!dep[ver[i]])dep[ver[i]]=dep[cur]+1, q.push(ver[i]);
        }
        return false;
    }
    ll dfs(int x,ll flow,int t){
        if(x==t || !flow)return flow;
        ll rest = flow, tmp;
        for(int i=tmphea[x];i&&rest;i=nex[i]){
            tmphea[x]=i;
            if(dep[ver[i]]==dep[x]+1 && edg[i]>0){
                if(!(tmp=dfs(ver[i],min(edg[i], rest),t)))dep[ver[i]]=0;
                edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
            }
        }
        return flow-rest;
    }
    inline ll solve(int s,int t){
        sum = 0;
        while(bfs(s,t))sum+=dfs(s,inf,t);
        return sum;
    }
}G;

bool vis[Maxn];

vector<int> G2[Maxn];

int dfn[Maxn], low[Maxn], sta[Maxn], Time, tp;
bool ins[Maxn];

int scc,bel[Maxn];
void tarjan(int u){
    dfn[u]=low[u]=++Time, sta[++tp]=u, ins[u]=1;
    for(auto v:G2[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(ins[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u] == low[u]){
        scc ++;
        do{ u = sta[tp], tp--;ins[u]=false, bel[u]=scc;}
        while(dfn[u]!=low[u]);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;
    int s=0, t=n*2+1;

    vector<int> id(n+1);

    for(int i=1;i<=n;i++){
        G.add_edge(s, i+n, 1);
        id[i] = G.add_edge(i, t ,1);
        G.add_edge(i, i+n, 1e9);
    }
    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        G.add_edge(u+n, v, 1e9);
    }

    // u 在反链里 等价节点 u 在 T 里面且 u+n 在 S 里面

    cout << n - G.solve(s, t) << '\n';

    vis[s] = 1;
    queue<int> q;q.push(s);
    while(q.size()){
        int u = q.front(); q.pop();
        for(int i=G.hea[u];i;i=G.nex[i]){
            if(G.edg[i] && !vis[G.ver[i]]){
                vis[G.ver[i]] = 1;
                q.push(G.ver[i]);
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(!vis[i] && vis[i+n])cout<<1;
        else cout<<0;
    }
    cout<<'\n';

    for(int i=0;i<=t;i++){
        for(int j=G.hea[i];j;j=G.nex[j]){
            if(G.edg[j]){
                G2[i].push_back(G.ver[j]);
            }
        }
    }

    for(int i=0;i<=t;i++){
        if(!dfn[i])tarjan(i);
    }

    for(int i=1;i<=n;i++){
        if(bel[i+n] == bel[t] || bel[i]==bel[i+n] || bel[i]==bel[s])cout << 0 ;
        else cout <<1;
    }
    cout<<'\n';
    return 0;
}

练习
https://www.luogu.com.cn/problem/AT_abc237_h

参考资料