[網絡流24題] 搭配飛行員

★★☆?? 輸入文件：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可以同機飛行。 注:正駕駛員的編號在前,即正駕駛員的編號小于副駕駛員的編號. 【輸出格式】 輸出文件有一行
第一行，1個整數，表示最大起飛的飛機數。 【輸入輸出樣例】 輸入文件名： flyer.in 10 5?
1 7?
2 6?
2 10?
3 7?
4 8?
5 9?
? 輸出文件名：flyer.out 4 記錄個板子~~~ 1 #include<cmath> 2 #include<queue> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 #define INF 1000 9 using namespace std; 10 struct node{ 11 int u,v,w,nxt; 12 }g[60010]; 13 int adj[60010],e; 14 void add(int u,int v,int w){ 15 g[e].v=v; g[e].u=u; g[e].w=w; 16 g[e].nxt=adj[u]; adj[u]=e++; 17 } 18 int n,m; 19 int S,T; 20 int dep[210]; 21 bool BFS(){ 22 memset(dep,0,sizeof(dep)); 23 queue<int> q; int k; 24 q.push(S),dep[S]=1; 25 while(!q.empty()){ 26 k=q.front(); q.pop(); 27 for(int i=adj[k];i!=-1;i=g[i].nxt){ 28 int v=g[i].v; 29 if(g[i].w && (!dep[v])){ 30 dep[v]=dep[k]+1; 31 q.push(v); 32 if(v==T) return 1; 33 } 34 } 35 } 36 return 0; 37 } 38 int dfs(int x,int fw){ 39 //printf("x==%d fw=%d\n",x,fw); 40 if(x==T) return fw; 41 int tmp = fw,k; 42 for(int i=adj[x];i!=-1;i=g[i].nxt){ 43 int v=g[i].v; 44 if(g[i].w && tmp && dep[v]==dep[x]+1){ 45 //cout<<"w== "<<g[i].w<<endl; 46 k=dfs(v,min(g[i].w,tmp)); 47 if(!k){ 48 dep[v]=0; 49 continue; 50 } 51 g[i].w-=k; g[i^1].w+=k; tmp-=k; 52 } 53 } 54 return fw-tmp; 55 56 } 57 void ot(); 58 int main(){ 59 freopen("flyer.in","r",stdin); 60 freopen("flyer.out","w",stdout); 61 scanf("%d%d",&n,&m); 62 int x,y; 63 S=0; T=110; 64 memset(adj,-1,sizeof(adj)); 65 for(int i=1;i<=n;i++){ 66 if(i<=m){ 67 add(S,i,1); add(i,S,0); 68 } 69 else{ 70 add(i,T,1); add(T,i,0); 71 } 72 } 73 while(scanf("%d%d",&x,&y)==2){ 74 add(x,y,1); add(y,x,0); 75 } 76 int sum=0; 77 int ans=0; 78 while(BFS()){ 79 //ot(); 80 while(sum=dfs(S,INF)){ 81 ans+=sum; 82 //cout<<"ans== "<<ans<<endl; 83 } 84 } 85 cout<<ans<<endl; 86 return 0; 87 }

?

轉載于:https://www.cnblogs.com/FOXYY/p/7265789.html

總結

以上是生活随笔為你收集整理的搭配飞行员 dinic的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。