洛谷 P2756——飞行员配对方案问题【二分图最大匹配问题 & 最大流Dinic算法】

题目传送门

---

题目背景

第二次世界大战时期…

---

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

---

输入格式

第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。

接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。

---

输出格式

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

---

输入

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

---

输出

4
1 7
2 9
3 8
5 10

---

题解

• 很明显的二分图最大匹配，但是我们可以转换成最大流问题
• 添加一个源点和汇点，然后边权全设置为1，跑一边Dinic即可
  

---

AC-Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int inf = 0x3f3f3f3f;
const int maxn = 50 * 50 + 50 * 2;
int n, m;

struct Edge {
	int to;
	int next;
	int val;
}edge[maxn << 1]; // 双向边，开 2 倍数组
int head[maxn];
int cnt; // 边的数量，从 0 开始编号
int depth[maxn]; // 分层图标记深度
int cur[maxn]; // 当前弧优化，记录当前点 u 循环到了哪一条边
void add(int u, int v, int w) {
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	edge[cnt].val = w;
	head[u] = cnt++;
}

// bfs分层图
bool bfs(int s, int t) {
	queue<int>q;
	memset(depth, 0, sizeof depth);
	depth[s] = 1; // 源点深度为 1
	cur[s] = head[s];
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (edge[i].val > 0 && depth[v] == 0) { // 如果残量不为0，且 v 还未分配深度
				depth[v] = depth[u] + 1;
				cur[v] = head[v]; //------当前弧优化，注意在bfs里，这样做到了“按需赋值”，因为Dinic本来上界就松得一匹, BFS的过程中不连通的点根本就不用再管了...
				if (v == t) // -----分层图汇点优化：遇到汇点直接返回------
					return true;
				q.push(v);
			}
		}
	}
	return depth[t]; // 汇点深度为 0：不存在分层图，返回false；
					 //           非 0 ：存在增广路，返回true
}

// dfs寻找增广路
int dfs(int u, int flow, int t) {
	if (u == t || flow <= 0) // 到达汇点
		return flow;
	int rest = flow;
	for (int i = cur[u]; ~i; i = edge[i].next) {
		int v = edge[i].to;
		if (depth[v] == depth[u] + 1 && edge[i].val != 0) { // 满足分层图、残量>0 两个条件
			int k = dfs(v, min(rest, edge[i].val), t); // 向下增广
			if (k < 0) // ------无用点优化-----
				depth[v] = 0;
			rest -= k;
			edge[i].val -= k; // 正向边减
			edge[i ^ 1].val += k; // 反向边加
			if (rest <= 0) //------剩余量优化：在进行增广的时候，如果该节点已经没有流量，直接退出------
				break;
		}
	}
	return flow - rest; // flow：推送量，rest：淤积量，flow - rest：接受量/成功传递量
}
int Dinic(int s, int t) {
	int ans = 0;
	while (bfs(s, t)) {
		ans += dfs(s, inf, t);
	}
	return ans;
}
int main() {
	ios;
	while (cin >> m >> n) {
		::cnt = 0;
		memset(head, -1, sizeof head);
		for (int i = 1; i <= m; i++) {
			add(0, i, 1);
			add(i, 0, 0);
		}
		for (int i = m + 1; i <= n; i++) {
			add(i, n + 1, 1);
			add(n + 1, i, 0);
		}
		for (int a, b; cin >> a >> b;) {
			if (a == -1 && b == -1)		break;
			add(a, b, 1);
			add(b, a, 0);
		}
		int ans = Dinic(0, n + 1);
		if (ans) {
			cout << ans << endl;
			for (int i = 1; i <= m; i++) {
				for (int u = head[i]; ~u; u = edge[u].next) {
					if (edge[u].to == 0)	continue;
					if (edge[u].val == 0) {
						cout << i << " " << edge[u].to << endl;
						break;
					}
				}
			}
		}
		else {
			cout << "No Solution!" << endl;
		}

	}
}