最大流

2020-03-07

数据结构与算法

字数统计: 780字 | 阅读时长≈ 4分钟

最大流的总结

P2756 飞行员配对方案问题(最大流)

题目链接

https://www.luogu.org/problem/P2756

解题思路

分源点、汇点，源点连英国飞行员点（流量为1）、每个英国飞行员点连可配合的外籍飞行员点（流量为1）、每个外籍飞行员点连汇点（流量为1），跑最大流即可。

AC代码

1	复制#include <bits/stdc++.h>
2	#define go(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
3	#define dip(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
4	#define maxn 2010
5	#define maxm 1200010
6	#define inf 0x3f3f3f3f
7	using namespace std;
8	struct Edge{
9	int to, nex, cap, flow;
10	}edge[maxm];
11	int tol;
12	int head[maxn];
13	void init(){
14	tol = 2;
15	memset(head, -1, sizeof(head));
16	}
17	void addedge(int u, int v, int w, int rw = 0){
18	edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
19	edge[tol].nex = head[u]; head[u] = tol++;
20	edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
21	edge[tol].nex = head[v]; head[v] = tol++;
22	}
23	int Q[maxn];
24	int dep[maxn], cur[maxn], sta[maxn];
25	bool bfs(int s, int t, int n){
26	int fro = 0, tail = 0;
27	memset(dep, -1, sizeof(dep[0]) * (n + 1));
28	dep[s] = 0;
29	Q[tail++] = s;
30	while(fro < tail){
31	int u = Q[fro++];
32	for(int i = head[u]; i != -1; i = edge[i].nex){
33	int v = edge[i].to;
34	if(edge[i].cap > edge[i].flow && dep[v] == -1){
35	dep[v] = dep[u] + 1;
36	if(v == t){return true;}
37	Q[tail++] = v;
38	}
39	}
40	}
41	return false;
42	}
43	int dinic(int s, int t, int n){
44	int maxflow = 0;
45	while(bfs(s, t, n)){
46	for(int i = 0; i < n; i++)cur[i] = head[i];
47	int u = s, tail = 0;
48	while(cur[s] != -1){
49	if(u == t){
50	int tp = inf;
51	for(int i = tail - 1; i >= 0; i--)
52	tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
53	maxflow += tp;
54	for(int i = tail - 1; i >= 0; i--){
55	edge[sta[i]].flow += tp;
56	edge[sta[i]^1].flow -= tp;
57	if(edge[sta[i]].cap-edge[sta[i]].flow == 0)tail = i;
58	}
59	u = edge[sta[tail]^1].to;
60	}
61	else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]){
62	sta[tail++] = cur[u];
63	u = edge[cur[u]].to;
64	}
65	else {
66	while(u != s && cur[u] == -1)
67	u = edge[sta[--tail]^1].to;
68	cur[u] = edge[cur[u]].nex;
69	}
70	}
71	}
72	return maxflow;
73	}
74	int main()
75	{
76	int n, m, u, v;
77	scanf("%d %d %d %d", &n, &m, &u, &v);
78	init();
79	while(u != -1 && v != -1){
80	addedge(u, v + n, 1);
81	scanf("%d %d", &u, &v);
82	}
83	go(i,1,n)addedge(0, i, 1);
84	go(i,1,m)addedge(i + n, n + m + 1, 1);
85	int ans = dinic(0, n + m + 1, n + m + 2);
86	if(!ans){printf("No Solution!\n"); return 0;}
87	printf("%d\n", ans);
88	go(i,1,n){
89	for(int j = head[i]; j != -1; j = edge[j].nex){
90	if(edge[j].flow == 1)printf("%d %d\n", i, edge[j].to - n);
91	}
92	}
93	return 0;
94	}