★★☆ 输入文件:flyer.in
输出文件:flyer.out
简单对比
时间限制:1 s 内存限制:128 MB
【问题描述】
飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。
如图,假设有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
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 const int maxn=110,maxm=110*110; 11 struct Edge{ 12 int to,next,rest; 13 }e[maxm]; 14 int head[maxn]; 15 int ecnt=1; 16 inline void addedge(int x,int y,int r){ 17 e[++ecnt].to=y; e[ecnt].rest=r; e[ecnt].next=head[x]; head[x]=ecnt; 18 e[++ecnt].to=x; e[ecnt].rest=0; e[ecnt].next=head[y]; head[y]=ecnt; 19 } 20 int N,M,S,T,ANS; 21 int dis[maxn]; 22 23 bool BFS(){ 24 memset(dis,0,sizeof(dis)); 25 dis[S]=1; 26 static queue<int> Q; 27 while(!Q.empty()) Q.pop(); 28 Q.push(S); 29 while(!Q.empty()){ 30 int x=Q.front(); Q.pop(); 31 for(int i=head[x];i;i=e[i].next){ 32 int y=e[i].to; 33 if(e[i].rest&&dis[y]==0){ 34 dis[y]=dis[x]+1; 35 Q.push(y); 36 } 37 } 38 } 39 if(dis[T]) return true; 40 return false; 41 } 42 int DFS(int x,int flow){ 43 if(x==T) return flow; 44 int now=0,tmp; 45 for(int i=head[x];i;i=e[i].next){ 46 if(e[i].rest&&dis[e[i].to]==dis[x]+1){ 47 tmp=DFS(e[i].to,min(flow-now,e[i].rest)); 48 e[i].rest-=tmp; 49 e[i^1].rest+=tmp; 50 now+=tmp; 51 if(now==flow) return now; 52 } 53 } 54 if(!now) dis[x]=0; 55 return now; 56 } 57 int dinic(){ 58 int ans=0; 59 while(BFS()){ 60 ans+=DFS(S,1e9); 61 } 62 return ans; 63 } 64 int main(){ 65 scanf("%d%d",&N,&M); 66 S=0; T=N+1; 67 int u,v; 68 while(scanf("%d%d",&u,&v)!=EOF) addedge(u,v,1); 69 for(int i=1;i<=M;i++) addedge(S,i,1); 70 for(int i=M+1;i<=N;i++) addedge(i,T,1); 71 ANS=dinic(); 72 printf("%d",ANS); 73 return 0; 74 }