【网络流24题专题】2 · 较简单的最大流

包括以下较为简单的可以用最大流解决的问题:

loj#6000 搭配飞行员loj#6006 试题库loj#6004 圆桌聚餐loj#6002 最小路径覆盖

搭配飞行员

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

这显而易见的就是一个二分图匹配的问题。考虑 $\rm S$ 向左部每个点连 $f=1$ 的边,右部的向 $\rm T$ 连 $f=1$ 的边。考虑一组匹配会贡献 $1$ 的流量,且每个点只有 $1$ 的原始流保证了只可使用一次,所以不难证明是但俺就是最大流。

1
2
3
4
5
6
7
8
int main(){
cin >> N >> M ;
fill(head, head + N + 30, -1); S = 0, T = N + 1 ;
while(cin >> A >> B) add(A, B, 23333), add(B, A, 0) ;
for(i = 1; i <= M ; i ++) add(S, i, 1), add(i, S, 0) ;
for(i = M + 1; i <= N ; i ++) add(i, T, 1), add(T, i, 0) ;
cout << Dinic() << endl ; return 0 ;
}

试题库

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

很水的建模,$\rm S$ 向每个题连 $f=1$ 的边表示只能用一次,每个题向对应的类型连边,每个类型向 $\rm T$ 连 $f=need_x$ 的边。然后输出方案就只需要看一下每个类型连的边有谁 $f$ 被流成 $0$ 了即可。

很久之前的 Dinic 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(){
cin >> K >> N, T = N + K + 1 ;
cnt = -1, memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i) Add(S, i, 1) ; L1 = cnt + 1 ;
for (i = N + 1 ; i <= N + K ; ++ i)
scanf("%d", &x), w1 += x, Add(i, T, x) ;
R1 = cnt ; L2 = R1 + 1 ;
for (i = 1 ; i <= N ; ++ i){
scanf("%d", &x) ;
while (x --) cin >> y, Add(i, N + y, 1) ;
} R2 = cnt ;
while(BFS()){
for (i = 0 ; i <= T ; ++ i) cur[i] = head[i] ;
w += dfs(S, T, Inf) ;
}
if (w != w1) return puts("No Solution!"), 0 ;
for (i = L2 ; i < R2 ; i += 2)
if (!E[i].f) Ans[to(i) - N].push_back(E[i].fr) ;
for (i = 1 ; i <= K ; ++ i, cout << endl)
for (cout << i << ": ", j = 0 ; j < Ans[i].size() ; ++ j) cout << Ans[i][j] << " " ; return 0 ;
}

圆桌聚餐

假设有来自 $n$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$。会议餐厅共有 $m$ 张餐桌,每张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。

发现是一个特殊的匹配问题,考虑从 $\rm S$ 到每个单位连 $f=r_i$ 的边,每个桌子向 $\rm T$ 连一条 $f=c_i$ 的边,同时每个单位和每张桌子之间连 $f=1$ 的边。这样就可以控制每个单位至多一个在某个餐桌。同样,如果限制同一张餐桌不能做超过 $k$ 个同一单位的人,只需要把 $f$ 从 $1$ 改成 $k$ 即可。

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
#define to(k) e[k].to
#define fw(k) e[k].flow
#define next(k) e[k].next

const int M = 2010 ;
const int N = 200010 ;

int cnt ;
int res ;
int n, m ;
int h[N] ;
int gap[N] ;
int vis[N] ;
int _s, _t ;
int A[M][M] ;
int head[N] ;
int extra[N] ;
queue <int> q ;
struct ed{
int to ;
int flow ;
int next ;
}e[N * 2] ;
struct state{
int h, num ;
bool operator <(const state & now)
const { return h < now.h ; }
} ;
priority_queue <state> p ;

int add(int a, int b, int c){
to(++ cnt) = b ; fw(cnt) = c ;
next(cnt) = head[a] ; head[a] = cnt ;
return cnt ;
}
void bfs(){
q.push(_t) ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
for (int k = head[x] ; ~k ; k = next(k))
if (h[to(k)] >= n + 1)
h[to(k)] = h[x] + 1, q.push(to(k)) ;
}
}
int HLPP(){
//cout << cnt << endl ;
h[_t] = 0 ; bfs() ; h[_s] = n ;
for (int k = head[_s] ; ~k ; k = next(k)){
extra[to(k)] += fw(k) ;
fw(k ^ 1) = fw(k), fw(k) = 0 ;
if (to(k) != _t) vis[to(k)] = 1,
p.push((state){h[to(k)], to(k)}) ;
}
for (int i = 1 ; i <= n ; ++ i)
if (h[i] <= n + 1) gap[h[i]] ++ ;
//for (int i = 1 ; i <= n ; ++ i) cout << h[i] << endl ;
while (!p.empty()){
state y = p.top() ;
int minh = 1000000000 ;
int x = y.num ; vis[x] = 0 ; p.pop() ;
for (int k = head[x] ; ~k ; k = next(k)){
int val = min(fw(k), extra[x]) ;
if (val > 0 && h[to(k)] + 1 == h[x]){
fw(k) -= val ;
extra[x] -= val ;
fw(k ^ 1) += val ;
extra[to(k)] += val ;
if (to(k) == _s || to(k) == _t) continue ;
if (!vis[to(k)]) vis[to(k)] = 1,
p.push((state){h[to(k)], to(k)}) ;
}
if (!extra[x]) break ;
if (fw(k)) minh = min(minh, h[to(k)]) ;
}
if (extra[x]){
if (! -- gap[h[x]]){
for (int i = 1 ; i <= n ; ++ i)
if (i != _s && i != _t && h[i] > h[x] && h[i] < n + 1)
gap[h[i]] --, h[i] = n + 1, gap[h[i]] ++ ;
}
gap[h[x] = minh + 1] ++ ; p.push((state){h[x], x}) ; vis[x] = 1 ;
}
}
return extra[_t] ;
}
void Init(){
cnt = -1 ;
for (int i = 1 ; i <= n ; ++ i)
head[i] = -1, h[i] = 1000000000 ;
}
int main(){
int nn, mm ;
int u, v, w ;
cin >> nn >> mm ;
n = nn + mm + 2 ;
_s = 1, _t = n ; Init() ;
for (int i = 1 ; i <= nn ; ++ i)
cin >> w, res += w,
add(_s, i + 1, w), add(i + 1, _s, 0) ;
for (int i = 1 ; i <= mm ; ++ i)
cin >> w, add(i + nn + 1, _t, w), add(_t, i + nn + 1, 0) ;
for (int i = 1 ; i <= nn ; ++ i)
for (int j = 1 ; j <= mm ; ++ j)
A[i][j] = add(i + 1, j + nn + 1, 1), add(j + nn + 1, i + 1, 0) ;
if (HLPP() < res)
return puts("0"), 0 ;
else{
puts("1") ;
for (int i = 1 ; i <= nn ; ++ i){
for (int j = 1 ; j <= mm ; ++ j)
if (fw(A[i][j]) == 0) cout << j << " " ;
puts("") ;
}
}
return 0 ;
}

最小路径覆盖问题

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

嗯,这道题大概是教了一下怎么拆点。考虑对于每个点 $v$,新建一个替身点 $v’$ 。原图中的路径 $(u,v)$ 变换为 $(u,v’)$ ,然后 $\rm S$ 向所有 $v$ 连边,所有 $v’$ 向 $\rm T$ 连边。思考这么做本质上是在求一个匹配,最后没有匹配的到左部的一个右部点可以看做是一条路径的结尾。那么考虑这样跑完一组匹配之后,所有没有匹配上的点都是一条路径的结尾,也就是路径的数量。所以跑一个最大流,就可以得到最少的路径数量,也就是最小路径匹配。

这代码还是上古时期拿 dinic 写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
memset(head, -1, sizeof(head)) ;
cin >> N >> M, T = N << 1 | 1, S = 0 ;
for (i = 1 ; i <= N ; ++ i)
Add(S, i, 1), Add(i + N, T, 1) ;
for (i = 1 ; i <= M ; ++ i)
scanf("%d%d", &A, &B), Add(A, B + N, 1) ;
while (BFS()) {
for (i = 0 ; i <= T ; ++ i) cur[i] = head[i] ;
Ans += dfs(S, T, Inf) ;
}
for (i = 1 ; i <= N ; ++ i) fa[i] = i ;
for(i = 0 ; i <= cnt ; ++ i)
if (fr(i) >= 1 && fr(i) <= N && to(i) < T && to(i) > N && !E[i].f)
fa[find(to(i) - N)] = find(fa[fr(i)]) ;
for (i = 1 ; i <= N ; ++ i)
if (fa[i] == i) begin_output(i), puts("") ;
cout << N - Ans << endl ; return 0 ;
}

那么不难看出建虚点这个操作的目的,就是限制每个点的经过次数。