[题解] [网络流二十四题（一）] 飞行员配对方案问题 （二分图匹配）

1.飞行员配对方案问题

题目描述 Description
第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员，其中1名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机
输入描述 Input Description
第1行有2个正整数m和n。n是皇家空军的飞行员总数(n<100)；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n。接下来每行有2个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。文件最后以2个-1结束。
输出描述 Output Description
第1行是最佳飞行员配对方案一次能派出的最多的飞机数M。接下来M行是最佳飞行员配对方案。每行有2个正整数i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j 配对。
如果所求的最佳飞行员配对方案不存在，则输出”No Solution!”
样例输入 Sample Input
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
样例输出 Sample Output
4
1 7
2 9
3 8
5 10

分析： 简单来说，如果图中点可以被分为两组，并且使得所有边都连接两组，则这就是一个二分图。我们显然可以将飞行员分为两组，一组英国飞行员，一组外籍飞行员，每组成员之间是不能够相互连边也不会相互连边的，所以建图后跑一边二分图最大匹配即可
建图： S向每个外籍飞行员连一条容量为1的边，每个外籍飞行员向自己可以配合的英国飞行员连一条容量为1边，每个英国飞行员向T连一条容量为1的边
　　
Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005,maxm = 100005;
struct node{
int to;
int next;
int flow;
}e[maxm*2];
int d[maxn];
int f[maxn];
int head[maxn],cur[maxn];
int n,m,tot,s,t;
int read() {
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
void addedge(int u,int v,int c) {
    e[++tot].to=v;
    e[tot].flow=c;
    e[tot].next=head[u];
    head[u]=tot;
    e[++tot].to=u;
    e[tot].flow=0;
    e[tot].next=head[v];
    head[v]=tot;
return ;
}

int dfs(int now,int flow) {
if(now==t)
return flow;
int use=0;
for(int i=cur[now];i;i=e[i].next) {
        cur[now]=i;
if(e[i].flow>0&&d[e[i].to]+1==d[now]) {
int tmp=dfs(e[i].to,min(e[i].flow,flow-use));
            use+=tmp;
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
if(flow==use)
return use;
        }
    }
    cur[now]=head[now];

if(!(--f[d[now]]))
        d[s]=m+2;//gap
    ++f[++d[now]];

return use;
}
int main() {
    tot=1;
    n=read(),m=read();
    s=0;t=m+1;
while(1) {
int a=read(),b=read();
if(a==-1 && b==-1) break;
        addedge(a,b,1);
    }
for(int i=1;i<=n;i++)
        addedge(s,i,1);
for(int i=n+1;i<=m;i++)
        addedge(i,t,1);

    f[0]=m+2;
int ans=0;
while(d[s]<m+2)
        ans+=dfs(s,1<<30);
if(!ans)
printf("No Solution!");
else {
printf("%d\n",ans);
for(int i=2;i<=tot;i+=2) {
if(e[i].to==s || e[i^1].to==s) continue;
if(e[i].to==t || e[i^1].to==t) continue;
if(e[i^1].flow!=0)
printf("%d %d\n",e[i].to,e[i^1].to);
        }
    }

return 0;
}