「LOJ6002」「网络流 24 题」最小路径覆盖

Description

给定有向图G=(V,E)G = (V, E)。设PPGG的一个简单路(顶点不相交)的集合。如果VV中每个顶点恰好在PP的一条路上,则称PPGG的一个路径覆盖。PP中路径可以从VV的任何一个顶点开始,长度也是任意的,特别地,可以为00GG的最小路径覆盖是GG的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图GG的最小路径覆盖。

Input

11行有22个正整数nnmmnn是给定有向无环图GG的顶点数,mmGG的边数。
接下来的mm行,每行有22个正整数uuvv,表示一条有向边(i,j)(i, j)

Output

从第11行开始,每行输出一条路径。
文件的最后一行是最少路径数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

Sample Output

1
2
3
4
1 4 7 10 11
2 5 8
3 6 9
3

HINT

1n200,1m60001 \leq n \leq 200, 1 \leq m \leq 6000

Solution

有向无环图

链:一条链是一些点的集合,链上任意两个点xx,yy,满足要么 x 能到达yy,要么yy能到达xx

反链:一条反链是一些点的集合,链上任意两个点xx,yy,满足xx不能到达yy,且yy也不能到达xx

一个定理:最长反链长度 = 最小链覆盖
对偶定理:最长链长度 = 最小反链覆盖
至于证明,神仙去想吧…

std

原图最小路径覆盖=原点数n-二分图最大匹配
原图最小路径覆盖=原点数n-最大流
其中每个链不相交。
如果(x,y)(x,y)有边,连接(x,y+n)(x,y+n)容量为11
ss1n1\to n连容量为11的边
n+12nn + 1 \to 2ntt连容量为11的边。
跑个最大流。
方案嘛,显然容量为00的边就是一个方案,统计nxtnxt数组和prepre数组就好了。
如果你还不懂,你需要意会了。

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<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210*2, M = 6100;
struct Edge {
int u, v, f, nxt;
}e[M * 2];
int head[N], en = 1;
int n, m, s, t;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = 1;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int d[N];
bool bfs() {
queue<int>q;
q.push(s);
memset(d, 0, sizeof d);
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
// printf("x=%d\n", x);
for(int i = head[x]; i; i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1 && e[i].f) {
k = dinic(e[i].v, min(e[i].f, rest));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
int pre[N], nxt[N];
bool vis[N];
int main() {
n = read(), m = read();
s = n * 2+ 1;
t = n * 2 + 2;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y + n);
}
for(int i = 1; i <= n; ++i) {
addedge(s, i);
addedge(i + n, t);
}
int y, ans = 0;
while(bfs()) while(y = dinic(s, 1e9)) ans += y;
for(int i = 2; i <= en; i += 2)
if(e[i].f == 0) {
if(e[i].v > n) {
pre[e[i].v - n] = e[i].u;
nxt[e[i].u] = e[i].v - n;
}
}
for(int i = 1; i <= n; ++i) if(pre[i] == 0) {
int j = i;
while(j) {
printf("%d ", j);
j = nxt[j];
}
puts("");
}
writeln(n - ans);
return 0;
}