【問題描述】

飛行大隊有若干個來自各地的駕駛員，專門駕駛一種型號的飛機，這種飛機每架有兩個駕駛員,需一個正駕駛員和一個副駕駛員。由于種種原因，例如相互配合的問題，有些駕駛員不能在同一架飛機上飛行，問如何搭配駕駛員才能使出航的飛機最多。 如圖，假設有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個整數，表示最大起飛的飛機數。

【題解】

加上源點和匯點，求最大流（劉）。

【代碼】

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <iostream> #include <vector> #include <cmath> #include <stack> #include <queue> #define min(x,y) x<y?x:y #define max(x,y) x>y?x:y const int maxf=0x7fffffff; using namespace std;struct arr{int y,w,next; }a[1000001]; int n,m,nm,ans; int ls[4001],q[4001],ha[4001];void add(int u,int v,int z){nm++; a[nm].y=v; a[nm].w=z; a[nm].next=ls[u]; ls[u]=nm;nm++; a[nm].y=u; a[nm].next=ls[v]; ls[v]=nm; }void init(){nm=1; int x,y;scanf("%d %d",&m,&n);scanf("%d %d",&x,&y);while (x!=y and x!=-1){add(x,y,1);scanf("%d %d",&x,&y);}for(int i=1;i<=n;++i){if (i<=m) add(0,i,1);else add(i,n+1,1);} }bool bfs(){int x,t=0,w=1,p,i;memset(ha,-1,sizeof(ha));q[t]=ha[0]=0;while (t<w){x=q[t++];i=ls[x];while(i){if (a[i].w&&ha[a[i].y]<0){q[w++]=a[i].y;ha[a[i].y]=ha[x]+1;}i=a[i].next;}}if (ha[n+1]==-1) return 0;else return 1; }int dfs(int x,int maxf){if (x==n+1) return maxf;int i=ls[x];int w,used=0;while(i){if(a[i].w&&ha[a[i].y]==ha[x]+1){w=maxf-used;w=dfs(a[i].y,min(w,a[i].w));a[i].w-=w;a[i^1].w+=w;used+=w;if(used==maxf)return maxf;}i=a[i].next;}if (used==0) ha[x]=-1;return used; }void code(){ans=0;while (bfs()) ans+=dfs(0,maxf);if (ans!=0) printf("%d\n",ans);else printf("No Solution!"); }int main(){init();code();return 0; }

轉載于:https://www.cnblogs.com/zyx-crying/p/9319534.html

總結

以上是生活随笔為你收集整理的网络流24题1 飞行员配对方案问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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