P2756 飞行员配对方案问题
题目背景
第二次世界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。
接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。
输出格式：
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。
输入输出样例
输入样例#1：
5 101 71 82 62 92 103 73 84 74 85 10-1 -1
输出样例#1：
41 72 93 85 10
网络流
建一个原点和一个汇点，然后让原点与所有的第一类飞行员连边，第二种飞行员与汇点连流量为1的边，每两个配对的点之间连边（边权任意），然后跑网络流
#include#include #include #include #include #define N 100100#define maxn 9999999using namespace std;queue q;int n,m,x,y,tot=1,ans,s,e;int to[N],cap[N],lev[N],cnt[N],head[N],nextt[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}int add(int x,int y,int z){ ++tot;to[tot]=y,cap[tot]=z,nextt[tot]=head[x];head[x]=tot; ++tot;to[tot]=x,cap[tot]=0,nextt[tot]=head[y];head[y]=tot;}inline bool bfs(){ while(!q.empty()) q.pop(); for(int i=s;i<=e;i++) { lev[i]=-1; cnt[i]=head[i]; } q.push(s),lev[s]=0; while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=nextt[i]) { int t=to[i]; if(cap[i]>0&&lev[t]==-1) { lev[t]=lev[x]+1; q.push(t); if(t==e) return true; } } } return false;}int dinic(int x,int flow){ if(x==e) return flow; int rest=0,delta; for(int &i=cnt[x];i;i=nextt[i]) { int t=to[i]; if(cap[i]>0&&lev[t]==lev[x]+1) { delta=dinic(t,min(cap[i],flow-rest)); if(delta) { rest+=delta; cap[i]-=delta; cap[i^1]+=delta; if(rest==flow) break; } } } if(rest!=flow) lev[x]=-1; return rest;}int main(){ m=read(),n=read(); s=0,e=n+1; for(int i=1;i<=m;i++) add(s,i,1); for(int i=m+1;i<=n;i++) add(i,e,1); while(1) { x=read(),y=read(); if(x==-1&&y==-1) break; add(x,y,maxn); } while(bfs()) ans+=dinic(s,maxn); printf("%d\n",ans); if(ans==0) { printf("No Solution!\n"); return 0; } for(int i=1;i<=m;i++) for(int j=head[i];j;j=nextt[j]) { if(cap[j]==maxn||to[j]==s) continue; printf("%d %d\n",i,to[j]); } return 0;}
我们还可以用匈牙利算法来做这道题