飞行员配对方案

题解

二分图匹配。
设一个超级源点和一个超级汇点，建立源点->外籍飞行员->英国飞行员->汇点的网络。所有边的容量设为1。此时，每单位流到汇点的流量即代表一对合法配对，配对间互不干扰。

所以跑最大流即可得到最大匹配数。若想得到谁和谁配对的方案，则看看哪条边流量为0即可。

代码

#include <cstdio>
#include <cstring>
const int maxn=200+10;
const int maxm=10000+10;
const int INF=0x3f3f3f3f; 
int cur[maxn],head[maxn],nxt[maxm<<1],to[maxm<<1],val[maxm<<1];
int dep[maxn];
int n,m,s,t;
int tot=1,cnt=0;
struct edge
{
    int u,v;
    edge() {}
    edge(int x,int y) {u=x,v=y;}
}e[maxm];
struct Queue
{
	int a[maxn];
	int l,r;
	Queue() {l=1,r=0;}
	void push(int x) {a[++r]=x;}
	void pop() {l++;}
	int front() {return a[l];}
	bool empty() {return l>r;}
}q;

inline int min(int x,int y) {return x<y?x:y;}
void add(int u,int v,int w)
{
    nxt[++tot]=head[u];
    head[u]=tot;
    to[tot]=v;
    val[tot]=w;
}
bool bfs()
{
    memset(dep, 0x3f, sizeof(dep));
    dep[s]=0;
    q=Queue();
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=head[u];i;i=nxt[i])
        {
            int v=to[i]; 
            if (val[i]&&dep[v]>dep[u]+1)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        } 
    }
    return dep[t]<INF;
}
int dfs(int u,int minf)
{
    if (u==t)
        return minf;
    int used=0;
    for (int &i=cur[u];i;i=nxt[i])
    {
        int v=to[i];
        if (val[i]&&dep[v]==dep[u]+1)
        {
        	int flow=dfs(v, min(minf-used, val[i]));
            if (flow)
            {
                used+=flow;
                val[i]-=flow;
                val[i^1]+=flow;
                if (used==minf)
                    break; 
            }
        }
     }
     return used; 
}
int main()
{
    scanf("%d%d",&m,&n);
    s=0,t=m+n+1;
    int u=-1,v=-1;
    while(scanf("%d%d",&u,&v)&&u!=-1) 
    {
        add(u, v, 1),add(v, u, 0);
        e[++cnt]=edge(u, v);
    }
    for (int i=1;i<=m;i++)
        add(s, i, 1),add(i, s, 0);
    for (int i=m+1;i<=m+n;i++)
        add(i, t, 1),add(t, i, 0);

    int maxflow=0; 
    while(bfs())
    {
    	for (int i=0;i<=m+n;i++)
    		cur[i]=head[i];
    	maxflow+=dfs(s, INF);
    }
    printf("%d\n",maxflow);
    for (int i=1;i<=cnt;i++)
        if (!val[i<<1])
            printf("%d %d\n",e[i].u,e[i].v);
    return 0;
}