飛行員配對方案問題

​​P2756 飛行員配對方案問題​​

參考：「網絡流24題」 1. 飛行員配對方案問題

思路：這是個二分圖的比對問題，雖然之前寫過一遍了，再寫一遍溫習溫習也無妨。使用匈牙利算法

感覺參考部落格中有一句話特别經典，很能描述匈牙利算法的思路.....

👇 👇 👇 👇

「如果我除了她（v）還能追到别的妹子，我就把她讓給你。」——w對x如是說。

代碼：

// Created by CAD on 2019/10/5.
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

int x[105],y[105],g[105][105],vis[105];
int n,m;
bool dfs(int i)
{
    for(int j=m+1;j<=n;++j)
    {
        if(g[i][j]&&!vis[j])
        {
            vis[j]=1;
            if(!y[j]||dfs(y[j]))
            {
                x[i]=j,y[j]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    int u,v,ans=0;
    while(cin>>u>>v&&~u&&~v) g[u][v]=1;
    for(int i=1;i<=m;++i)
        if(!x[i])
            mst(vis,0),ans+=dfs(i);
    cout<<ans<<endl;
    for(int i=1;i<=m;++i)
        if(x[i])
            cout<<i<<" "<<x[i]<<endl;
    return 0;
}