二分图匹配——Luogu2756 [网络流24题]飞行员配对方案问题

https://www.luogu.org/problem/show?pid=2756
网络流24题之一
二分图匹配的裸题
我打了个dinic最大流过掉了
具体做法就是设一个超原点和一个超汇点，
然后超原点与每一位外籍飞行员连一条流量为1的边
超汇点与每一位英国飞行员连一条流量为1的边
然后跑一遍最大流就好了。。。

记录方案我卡了很久
在此感谢lzq大佬指教（woc把我程序改的啊。。。）
从超原点出发找到外籍飞行员，然后直接暴力判断是否满流即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dist[10001],nedge=-1,head[10001],nex[10001],p[10001],c[10001],m,n,s,t,x,y,z;
const ll inf=0x3f3f3f3f;
inline void addedge(ll x,ll y,ll z){
    nedge++;p[nedge]=y;
    c[nedge]=z;nex[nedge]=head[x];
    head[x]=nedge;
}
inline bool bfs(ll s,ll e){
    ll now;
queue<ll>q;
memset(dist,-1,sizeof dist);
    dist[s]=1;
    q.push(s);
while(!q.empty()){
        now=q.front();
        q.pop();
        ll k=head[now];
while(k>-1){
if(dist[p[k]]<0&&c[k]>0){
                dist[p[k]]=dist[now]+1;
                q.push(p[k]);
            }
            k=nex[k];
        }
    }
if (dist[e]>0) return 1;
return 0;
}
inline ll finds(ll x,ll low){
    ll a;
if(x==t)return low;
    ll k=head[x];
while(k>-1){
if(dist[x]+1==dist[p[k]]&&(a=finds(p[k],min(low,c[k])))){
            c[k]-=a;
            c[k^1]+=a;
return a;
        }
        k=nex[k];
    }
return 0;
}
inline ll dinic(ll s,ll e){
    ll flow=0;
while(bfs(s,e))
while(x=finds(s,inf))flow+=x;
return flow;
}
int main()
{
memset(p,-1,sizeof p);
memset(c,-1,sizeof c);
memset(nex,-1,sizeof nex);
memset(head,-1,sizeof head);
scanf("%lld%lld",&m,&n);
for(ll i=1;i<=m;i++){
        addedge(0,i,1);
        addedge(i,0,0);
    }
for(ll i=m+1;i<=n;i++){
        addedge(i,n+1,1);
        addedge(n+1,i,0);
    }
while(1){
scanf("%lld%lld",&x,&y);
if(x==-1)break;
        addedge(x,y,inf);
        addedge(y,x,0);
    }
    s=0;t=n+1;
printf("%lld\n",dinic(s,t));
for(int i=head[0];~i;i=nex[i])
if(c[i]==0) 
for(int j=head[p[i]];~j;j=nex[j])
if(c[j]==inf-1)printf("%lld %lld\n",p[i],p[j]);
return 0;
}

现在是已经入夏的5月中旬
机智的我用Hungary算法重打了这题！
Hungary记录方案就比网络流方便啦！因为在dfs的时候已经记录下了对应的点了，直接输出就行了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<string>
#include<ctime>
#include<queue>
#include<climits>
using namespace std;
int vis[100001],pp[100001],x,y,n,m;
int nedge=0,p[100001],nex[100001],head[100001];
inline void addedge(int a,int b){p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;}
inline bool dfs(int x,int y){
for(int k=head[x];k;k=nex[k])if(vis[p[k]]!=y){
        vis[p[k]]=y;
if(!pp[p[k]]||dfs(pp[p[k]],y)){
            pp[x]=p[k];
            pp[p[k]]=x;
return 1;
        }
    }
return 0;
}
inline void hungary(){
int ans=0;
for(int i=1;i<=n;i++)if(dfs(i,i))ans++;
if(!ans){puts("No Solution!");return;}
printf("%d\n",ans);
for(int i=1;i<=n;i++)if(pp[i])printf("%d %d\n",i,pp[i]);
}
int main()
{
scanf("%d%d",&n,&m);
while(1){
scanf("%d%d",&x,&y);if(x==-1)break;
        addedge(x,y);
    }
    hungary();
return 0;
}