二分图最大流建图方式:
1.源点S与每个外籍飞行员有向边连边，权值为1
2.每个英国本地飞行员与汇点连接有向边，权值为1
3根据题意，外籍与本地飞行员连接有向边，权值为1.
输出方式：
最后输出方案数：
当某个可行流被选了之后经过的所有正向边都会− = t -=t−=t.
最后中间外籍与本地飞行员连接关系的正向有向边如果为0，则此边为最小割集（已被选出）即最大流，
割集对应的点，就是选的方案
1.最大流
#include<bits/stdc++.h> using namespace std; const int N=110,M=20200,INF=0x3f3f3f3f; int h[N],e[M],f[M],ne[M],idx; int q[N],d[N],cur[N]; int n,m,S,T; void add(int a,int b,int c) { f[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; f[idx]=0,e[idx]=a,ne[idx]=h[b],h[b]=idx++; } bool bfs() { int hh=0,tt=0; memset(d,-1,sizeof d); q[0]=S,d[S]=0,cur[S]=h[S]; while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int ver=e[i]; if(d[ver]==-1&&f[i]) { d[ver]=d[t]+1; cur[ver]=h[ver];//当前弧优化 if(ver==T) return true; q[++tt]=ver; } } } return false; } int find(int u,int limit) { if(u==T) return limit; int flow=0; for(int i=cur[u];~i&&flow<limit;i=ne[i]) { cur[u]=i;//当前弧 int ver=e[i]; if(d[ver]==d[u]+1&&f[i]) { int t=find(ver,min(limit-flow,f[i])); if(!t) d[ver]=-1; f[i]-=t; f[i^1]+=t; flow+=t; } } return flow; } int dinic() { int r=0,flow; while(bfs()) { while(flow=find(S,INF)) r+=flow; } return r; } int main() { scanf("%d%d",&m,&n); S=0; T=n+1; memset(h,-1,sizeof(h)); for(int i=1;i<=m;i++) add(S,i,1); for(int i=m+1;i<=n;i++) add(i,T,1); int x,y; while(scanf("%d%d",&x,&y),x!=-1||y!=-1) { add(x,y,1); } printf("%d\n",dinic()); for(int i=0;i<idx;i+=2) { if(e[i]>m&&e[i]<n+1&&!f[i]) { printf("%d %d\n",e[i^1],e[i]); } } return 0; }
2.使用匈牙利算法：
#include<bits/stdc++.h> using namespace std; const int N=100,M=10000; int h[N],e[M],ne[M],idx; int n,m; int match[N]; bool st[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool find(int x) { for(int i=h[x];~i;i=ne[i]) { int j=e[i]; if(!st[j]) { st[j]=1; if(match[j]==0||find(match[j])) { match[j]=x; return true; } } } return false; } int main() { scanf("%d%d",&m,&n); memset(h,-1,sizeof h); int a,b; while(scanf("%d%d",&a,&b),a!=-1||b!=-1) { add(a,b); } int res=0; for(int i=1;i<=m;i++) { memset(st,0,sizeof st); if(find(i)) res++; } cout<<res<<"\n"; for(int i=m+1;i<=n;i++) { if(match[i]) cout<<match[i]<<' '<<i<<"\n"; } }
