题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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!’。
输入输出样例
输入样例#1： 复制
5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8 5 10 -1 -1
输出样例#1： 复制
4 1 7 2 9 3 8 5 10
这题没什么好讲的，就是一个裸的最大的二分图匹配。
恶心的一点就是打印方案。
网络流可以解决二分图问题；
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <queue> 5 #include <cstring> 6 #include <string> 7 #include <map> 8 using namespace std; 9 const int maxn = 2e5 + 10; 10 const int INF = 1e9 + 10; 11 typedef long long LL; 12 struct node { 13 int from, to, cap, flow; 14 }; 15 struct Dinic { 16 int n, m, s, t; 17 vector<node>nodes; 18 vector<int>g[maxn]; 19 int vis[maxn]; 20 int d[maxn]; 21 int cur[maxn]; 22 void clearall(int n) { 23 for (int i = 0 ; i < n ; i++) g[i].clear(); 24 nodes.clear(); 25 } 26 void clearflow() { 27 int len = nodes.size(); 28 for (int i = 0 ; i < len ; i++) nodes[i].flow = 0; 29 } 30 void add(int from, int to, int cap) { 31 nodes.push_back((node) { 32 from, to, cap, 0 33 }); 34 nodes.push_back((node) { 35 to, from, 0, 0 36 }); 37 m = nodes.size(); 38 g[from].push_back(m - 2); 39 g[to].push_back(m - 1); 40 } 41 bool bfs() { 42 memset(vis, 0, sizeof(vis)); 43 queue<int>q; 44 q.push(s); 45 d[s] = 0; 46 vis[s] = 1; 47 while(!q.empty()) { 48 int x = q.front(); 49 q.pop(); 50 int len = g[x].size(); 51 for (int i = 0 ; i < len ; i++) { 52 node &e = nodes[g[x][i]]; 53 if (!vis[e.to] && e.cap > e.flow ) { 54 vis[e.to] = 1; 55 d[e.to] = d[x] + 1; 56 q.push(e.to); 57 } 58 } 59 } 60 return vis[t]; 61 } 62 int dfs(int x, int a) { 63 if (x == t || a == 0) return a; 64 int flow = 0, f, len = g[x].size(); 65 for (int &i = cur[x] ; i < len ; i++) { 66 node & e = nodes[g[x][i]]; 67 if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0 ) { 68 e.flow += f; 69 nodes[g[x][i] ^ 1].flow -= f; 70 flow += f; 71 a -= f; 72 if (a == 0) break; 73 } 74 } 75 return flow; 76 } 77 int maxflow(int a, int b) { 78 s = a; 79 t = b; 80 int flow = 0; 81 while(bfs()) { 82 memset(cur, 0, sizeof(cur)); 83 flow += dfs(s, INF); 84 } 85 return flow; 86 } 87 vector<int>mincut() { 88 vector<int>ans; 89 int len = nodes.size(); 90 for (int i = 0 ; i < len ; i++) { 91 node & e = nodes[i]; 92 if ( vis[e.from] && !vis[e.to] && e.cap > 0 ) ans.push_back(i); 93 } 94 return ans; 95 } 96 void reduce() { 97 int len = nodes.size(); 98 for (int i = 0 ; i < len ; i++) nodes[i].cap -= nodes[i].flow; 99 } 100 void path() { 101 int sz = nodes.size(); 102 for(int i = 0; i < sz; i += 2) { 103 node & e = nodes[i]; 104 if(e.flow == 1 && e.from != s && e.to != t) 105 printf("%d %d ", e.from, e.to); 106 } 107 } 108 } f; 109 int main() { 110 int n, m; 111 scanf("%d%d", &m, &n); 112 int x, y, s = 0, t = n + 1; 113 while(1) { 114 scanf("%d%d", &x, &y); 115 if (x == -1 && y == -1 ) break; 116 f.add(x, y, 1); 117 } 118 for (int i = 1 ; i <= n ; i++) { 119 if (i <= m) f.add(0, i, 1); 120 else f.add(i, n + 1, 1); 121 } 122 int ret = f.maxflow(0, n + 1); 123 if (!ret) printf("No Solution! "); 124 else { 125 printf("%d ", ret); 126 f.path(); 127 } 128 return 0; 129 }