题解 P2756 【飞行员配对方案问题】

一道二分图匹配的裸题，那么既然放在网络流24题里，就不用匈牙利或者KM了 一切二分图匹配都可以用网络流来做。。 我们把s和1~m连流量为1的边（我的程序里m是n，n是m，习惯了。。），把t和m+1~n也连上流量为1的边。中间的边流量也赋为1（也有赋为inf的做法，都可以），对这张图求最大流，答案就是飞机数了。其实也就是相当于求最多可以流几条不同的路。 输出方案时，我们枚举中间的边，如果这条边的流量变为0了，说明这条边为最大流做了贡献，也就是这两个人成功匹配了，输出即可。如果把中间的边流量赋为inf，只要看这一条边的反向边的值是否为零，不为零即成功匹配。（个人觉得不用赋inf） dinic求最大流： ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int inf=1000000000; int n,m,cnt=-1,s,t; int head[100010],nxt[100010],to[100010],val[100010]; int cur[100010],dep[100010],q[1000010]; void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } bool bfs() { memset(dep,0,sizeof(dep)); q[1]=s,dep[s]=1; int l=0,r=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!dep[v] && val[i]) { dep[v]=dep[u]+1; q[++r]=v; } } } if(!dep[t]) return 0; return 1; } int dfs(int u,int flow) { if(u==t) return flow; for(int& i=cur[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dep[v]==dep[u]+1 && val[i]) { int res=dfs(v,min(flow,val[i])); val[i]-=res,val[i^1]+=res; if(res) return res; } } return 0; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); s=0,t=m+1; for(int i=1;i<=n;i++) addedge(s,i,1),addedge(i,s,0); for(int i=n+1;i<=m;i++) addedge(i,t,1),addedge(t,i,0); while(1) { int x,y; scanf("%d%d",&x,&y); if(x==-1 && y==-1) break; addedge(x,y,1); addedge(y,x,0); } int ans=0,res=0; while(bfs()) { for(int i=s;i<=t;i++) cur[i]=head[i]; while(int add=dfs(s,inf)) ans+=add; } cout<<ans<<endl; for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=nxt[j]) { if(to[j]==s || to[j^1]==s || to[j]==t || to[j^1]==t) continue; if(!val[j]) res++,cout<<i<<" "<<to[j]<<endl; } return 0; } ```