从Byvoid大神博客那里拿到的好题和数据~在此鸣谢。
问题描述：
第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出
的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞
行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英
国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的
外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空
军一次能派出最多的飞机。
«编程任务：
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，
使皇家空军一次能派出最多的飞机。
«数据输入：
由文件input.txt提供输入数据。文件第1 行有2个正整数m和n。n是皇家空军的飞行
员总数(n<100)；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n。
接下来每行有2 个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。文件最后以2
个-1 结束。
«结果输出:
程序运行结束时，将最佳飞行员配对方案输出到文件output.txt 中。第1 行是最佳飞行
员配对方案一次能派出的最多的飞机数M。接下来M 行是最佳飞行员配对方案。每行有2
个正整数i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j 配对。
如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。
问题的实质是对于一个映射A，找出一个包含最多元素的双射，这个双射的映射规则是A的子集。
比较容易想到加一个源点和汇点使之变为最大流问题。如果没想到会相当难解。
构图：
建立源点s到集合A（外籍飞行员）的容量为1的有向边（从源点指向A）
建立集合B（本土飞行员）到汇点t的容量为1的有向边（从B指向汇点）
根据题中所给映射建立A到B的容量为1的有向边。
求最大流的得到的流量即为最大匹配数，走过的边为一组可行解。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define rep(i,a,b) for(int i=a;i<=b;++i) 5 using namespace std; 6 int cap[110][110]; 7 int m,n,s,t; 8 int a[110]; 9 int flow[110][110]; 10 int p[110]; 11 int ansp[110]; 12 int f=0; 13 void Input() 14 { 15 memset(p,0,sizeof(p)); 16 memset(cap,0,sizeof(cap)); 17 scanf("%d%d",&m,&n); 18 int x,y; 19 while(scanf("%d%d",&x,&y)==2&&(x!=-1)&&(y!=-1)) 20 { 21 cap[x][y]=1; 22 } 23 s=0;t=n+1; 24 rep(i,1,m) 25 { 26 cap[s][i]=1; 27 } 28 rep(i,m+1,n) cap[i][t]=1; 29 // printf("n=%d,m=%d ",n,m); 30 } 31 void work() 32 { 33 queue<int> q; 34 memset(flow,0,sizeof(flow)); 35 for(;;) 36 { 37 memset(a,0,sizeof(a)); 38 a[s]=1e10; 39 q.push(s); 40 while(!q.empty()) 41 { 42 int u=q.front();q.pop(); 43 rep(i,0,n+1) 44 { 45 // printf("u=%d cap[u][%d]=%d ",u,i,cap[u][i]); 46 if(!a[i]&&cap[u][i]>flow[u][i]) 47 { 48 p[i]=u;q.push(i); 49 a[i]=a[u]<(cap[u][i]-flow[u][i])?a[u]:cap[u][i]-flow[u][i]; 50 // printf("u=%d i=%d a[i]=%d ",u,i,a[i]); 51 } 52 } 53 } 54 // printf("f=%d a[t]=%d ",f,a[t]); 55 if(a[t]==0) break; 56 for(int j=t;j!=s;j=p[j]) 57 { 58 flow[p[j]][j]+=a[t]; 59 flow[j][p[j]]-=a[t]; 60 ansp[j]=p[j]; 61 } 62 f+=a[t]; 63 } 64 } 65 void pout() 66 { 67 if(f==0) printf("No Solution!"); 68 else 69 { 70 printf("%d ",f); 71 rep(i,m+1,n) 72 { 73 if(ansp[i]) 74 { 75 printf("%d %d ",ansp[i],i); 76 } 77 } 78 } 79 } 80 int main() 81 { 82 freopen("air3.in","r",stdin); 83 //freopen("a.out","w",stdout); 84 Input(); 85 work(); 86 pout(); 87 return 0; 88 }