题面

洛谷 P2756 飞行员配对方案问题

LOJ #6000.「网络流 24 题」搭配飞行员

因为 LOJ 上的版本比较简洁，所以就放这个版本的题面了。

飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员（英国）和一个副驾驶员（外籍）。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

思路

二分图匹配问题。可以使用匈牙利算法解决，也可用网络流求解。

如果一个英国驾驶员可以配对一个外籍驾驶员，那么就将他们两个连一条边（权值为 $1$ ）。

然后定义 S 点和 T 点分别为源点和汇点。因为数据很小，所以这里我将 S 点和 T 点编号分别定为 2333 和 2334。

将 S 与所有英国驾驶员连一条边，T 与所有外籍驾驶员连一条边。

然后求从 S 到 T 的最大流即可。

注意

洛谷版本的题面需要输出配对方案，我们用 $res[i]$ 来表示 $i$ 点的上一个点，在 EK 时更新这个数组即可。

代码

洛谷版本

#include<bits/stdc++.h>
using namespace std;
long long n,m,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005];
long long res[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(p,-1,sizeof(p));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (v[j]||s[i]<=0){
                continue;
            }
            p[j].from=now;
            p[j].edge=i;
            if (j==T){
                return 1;
            }
            q.push(j);
            v[j]=1;
        }
    }
    return 0;
}
long long EK(long long S,long long T){
    long long ans=0;
    while (bfs(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            res[p[i].from]=i;//记录配对方案
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
    }
    return ans;
}
int main(){
    int S=2333,T=2334;
    cin>>m>>n;
    for (int i=1;i<=m;i++){
    	add(S,i,1);
        add(i,S,0);
    }
    for (int i=1;i<=n;i++){
        add(i+n,T,1);
    	add(T,i+n,0);
    }
    while (1){
        int a,b;
        cin>>a>>b;
        if (a==-1&&b==-1){
        	break;
        }
        add(a,b+n,1);
        add(b+n,a,0);
    }
    cout<<EK(S,T)<<endl;
    for (int i=1;i<=n;i++){
    	if (res[i]){
    		cout<<i<<" "<<res[i]-n<<endl;
        }
    }
}

LOJ 版本

LOJ 上这道题更简单，不需要记录方案。但和洛谷上有一些细节的不同，需要注意。

#include<bits/stdc++.h>
using namespace std;
long long n,m,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(p,-1,sizeof(p));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (v[j]||s[i]<=0){
                continue;
            }
            p[j].from=now;
            p[j].edge=i;
            if (j==T){
                return 1;
            }
            q.push(j);
            v[j]=1;
        }
    }
    return 0;
}
long long EK(long long S,long long T){
    long long ans=0;
    while (bfs(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
    }
    return ans;
}
int main(){
	int S=2333,T=2334;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
    	add(S,i,1);
		add(i,S,0);
	}
    for (int i=1;i<=n;i++){
		add(i+n,T,1);
    	add(T,i+n,0);
	}
    int a,b;
    while (cin>>a>>b){
        add(a,b+n,1);
        add(b+n,a,0);
    }
    cout<<EK(S,T);
}