网络流24题——1736: 飞行员配对方案问题——二分图匹配

网络流24题——1736: 飞行员配对方案问题——二分图匹配

描述：

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

思路：

裸题

#include #include #include #include #include #include using namespace std;const int maxn = 1000;const int INF = 0x3f3f3f3f;int n, m, s, t;struct Edge { int from, to, flow, cap, flag; };struct Dinic { vector edges; vector G[maxn]; int level[maxn], cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap, int flag) { edges.push_back(Edge{from, to, 0, cap, flag}); edges.push_back(Edge{to, from, 0, 0, flag}); G[from].push_back(edges.size()-2); G[to].push_back(edges.size()-1); } int bfs() { memset(level, 0, sizeof(level)); level[s] = 1; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && !level[e.to]) { level[e.to] = level[u] + 1; q.push(e.to); } } } return level[t]; } int dfs(int u, int f) { if (u == t || !f) return f; for (int &i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && level[e.to] == level[u] + 1) { int d = dfs(e.to, min(f, e.cap - e.flow)); if (d > 0) { e.flow += d; edges[G[u][i]^1].flow -= d; return d; } } } return 0; } int maxflow() { int ans = 0, f; while (bfs()) { memset(cur, 0, sizeof(cur)); while ((f = dfs(s, INF))) ans += f; } return ans; }}ac;int main() { int x, y; scanf("%d%d", &x, &y); int temp = x; n = y; m = 0; ac.init(); while (~scanf("%d%d", &x, &y) && x != -1 && y != -1) { ac.addedge(x, y, 1, 1); m++; } for (int i = 1; i <= temp; i++) { ac.addedge(0, i, 1, 0); m++; } for (int i = temp+1; i <= n; i++) { ac.addedge(i, n+1, 1, 0); m++; } s = 0, t = n+1; printf("%d\n", ac.maxflow()); for (int i = 0; i < ac.edges.size(); i += 2) { if (ac.edges[i].flag == 1 && ac.edges[i].flow > 0) { printf("%d %d\n", ac.edges[i].from, ac.edges[i].to); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。