摘要：
14. [网络流24题] 搭配飞行员，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。请搭配飞行员，使出航的飞机最多。输入文件名：flyer.in1051726210374859输出文件名：flyer.out4思路：网络流裸题。
★★☆ 输入文件：flyer.in 输出文件：flyer.out简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。
![cogs 14. [网络流24题] 搭配飞行员第1张](http://www.cogs.pro/mw/images/2/24/Flyer.jpg)
如图，假设有10个驾驶员，如图中的V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行，就在代表他们两个之间连一条线,两个人不能同机飞行，就不连。例如V1和V7可以同机飞行，而V1和V8就不行。请搭配飞行员，使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.
【输入格式】
输入文件有若干行
第一行，两个整数n与n1，表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员.
下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。
第一行，两个整数n与n1，表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员.
下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。
注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号.
【输出格式】
输出文件有一行
第一行，1个整数，表示最大起飞的飞机数。
第一行，1个整数，表示最大起飞的飞机数。
【输入输出样例】
输入文件名： flyer.in
10 5
1 7
2 6
2 10
3 7
4 8
5 9
1 7
2 6
2 10
3 7
4 8
5 9
输出文件名：flyer.out
4
思路：网络流裸题。
网络流AC代码：
#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<algorithm> #define MAXN 20000 using namespacestd; queue<int>que; int n,n1,ans,tot=1,scr,decc; intlev[MAXN],cur[MAXN]; intto[MAXN],head[MAXN],net[MAXN],cap[MAXN]; void add(int u,int v,intw){ to[++tot]=v;net[tot]=head[u];cap[tot]=w;head[u]=tot; to[++tot]=u;net[tot]=head[v];cap[tot]=0;head[v]=tot; } boolbfs(){ for(int i=scr;i<=decc;i++){ lev[i]=-1; cur[i]=head[i]; } while(!que.empty()) que.pop(); que.push(scr); lev[scr]=0; while(!que.empty()){ int now=que.front(); que.pop(); for(int i=head[now];i;i=net[i]) if(cap[i]&&lev[to[i]]==-1){ lev[to[i]]=lev[now]+1; que.push(to[i]); if(to[i]==decc) return true; } } return false; } int dinic(int now,intflow){ if(now==decc) returnflow; int rest=0,detal; for(int & i=cur[now];i;i=net[i]) if(cap[i]&&lev[to[i]]==lev[now]+1){ detal=dinic(to[i],min(flow-rest,cap[i])); if(detal){ rest+=detal; cap[i]-=detal; cap[i^1]+=detal; if(rest==flow) break; } } if(rest!=flow) lev[now]=-1; returnrest; } intmain(){ freopen("flyer.in","r",stdin); freopen("flyer.out","w",stdout); scanf("%d%d",&n,&n1); intx,y; scr=0;decc=n+1; for(int i=1;i<=n1;i++) add(scr,i,1); for(int i=1;i<=n-n1;i++) add(i+n1,decc,1); while(scanf("%d%d",&x,&y)!=EOF) add(x,y,0x7f7f7f7f); while(bfs()) ans+=dinic(scr,0x7f7f7f7f); printf("%d",ans); }
匈牙利AC代码：
记住匈牙利算法的本质：有机会就上，就没机会也要创造机会上。
#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<algorithm> using namespacestd; int n,n1,ans,map[150][150],use[200],girl[200]; int find(intx){ for(int j=n1+1;j<=n;j++) if(use[j]==0&&map[x][j]==1){ use[j]=1; if(girl[j]==0||find(girl[j])){ girl[j]=x; return 1; } } return 0; } intmain(){ freopen("flyer.in","r",stdin); freopen("flyer.out","w",stdout); scanf("%d%d",&n,&n1); intx,y; while(scanf("%d%d",&x,&y)!=EOF) map[x][y]=1; for(int i=1;i<=n1;i++){ memset(use,0,sizeof(use)); if(find(i)) ans++; } printf("%d",ans); }