网络流24题
一、飞行员配对方案问题
题目背景
第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。
题目描述
一共有\(n\)个飞行员，其中有\(m\)个外籍飞行员和\((n−m)\)个英国飞行员，外籍飞行员从\(1\)到\(m\)编号，英国飞行员从\(m + 1\)到\(n\)编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
输入格式
输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 \(m\) 和飞行员总数 \(n\)。
从第二行起到倒数第二行，每行有两个整数 \(u, v，\)代表外籍飞行员 \(u\) 可以和英国飞行员 \(v\) 配合。
输入的最后一行保证为 -1 -1，代表输入结束。
输出格式
本题存在 Special Judge。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 \(k\)。
第 \(2\) 行到第 \(k+1\) 行，每行输出两个整数 \(u, v\)代表在你给出的方案中，外籍飞行员 \(u\) 和英国飞行员 \(v\) 配合。这 \(K\) 行的 \(u\) 与 \(v\) 应该互不相同。
题解
很显然这是二分图最大匹配问题，我们可以用匈牙利算法直接跑。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e2+50;
int m,n;//左右的集合的元素数量
int G[N][N];//邻接矩阵存图
int p[N] = {0};//右侧元素对应的左侧元素
bool vis[N];//记录右侧元素是否被访问过
bool match(int i){
for(int j = 1;j <= n;j++){
if(G[i][j] && !vis[j]){ //有边且未访问
vis[j] = true; //记录状态被访问过
if(p[j] == 0 || match(p[j])){ //暂无匹配,原匹配的左侧元素可以找到新元素
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}
}
}
return false; //循环结束，未找到匹配，返回匹配失败
}
int Hungarian(){
int cnt = 0;
for(int i = 1;i <= m;i++){
memset(vis,0,sizeof vis); //重置vis数组
if(match(i)) cnt++;
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
int x1,x2;
cin>>x1>>x2;
m = x1,n = x2-x1;//外fly,英fly
int u,v;
while(cin>>u>>v){
if(u == -1 && v == -1) break;
G[u][v-m] = 1;
}
int ans = Hungarian();
cout<<ans<<endl;
for(int i = 1;i <= n;i++){
if(p[i]) cout<<p[i]<<' '<<i+m<<endl;
}
return 0;
}
但是这是网络流的题解，所以就讲一下这个问题的网络流建图。
对于给定的二分图，增加超级源\(S\)和超级汇\(T\)。
1.\(S\)向\(X\)集合中每个顶点连一条容量为1的有向边
2.\(Y\)集合中每个顶点向\(T\)连一条容量为1的有向边
3.\(XY\)集合中的边，容量设为1（实际上多少都可以）
求最大流，流量即为匹配数，所有满流边就是一组可行解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=210;
const int maxm = 5e3+10;
ll level[maxn],head[2*maxm],cnt;
ll n,m;
ll ss,ee;
struct Edge{ll to,nxt,w;}edge[2*maxm];
void init(){
cnt=0;
memset(head,-1,sizeof head);
}
void add(ll u,ll v,ll w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].nxt=head[u];
head[u]=cnt++;
}
void add2(ll u,ll v,ll w,bool op){//是否为有向图
add(u,v,w);
add(v,u,op?0:w);
}
bool bfs(ll s,ll t){//分层图
queue<ll>q;
memset(level,0,sizeof level);
level[s]=1;
q.push(s);
while(!q.empty()){
ll x=q.front();
q.pop();
if(x==t)return true;
for(ll u=head[x];~u;u=edge[u].nxt){
ll v=edge[u].to,w=edge[u].w;
if(!level[v]&&w){
level[v]=level[x]+1;
q.push(v);
}
}
}
return false;
}
ll dfs(ll u,ll maxf,ll t){
if(u==t)return maxf;
ll ret=0;
for(ll i=head[u];~i;i=edge[i].nxt){
ll v=edge[i].to;ll w=edge[i].w;
if(level[u]+1==level[v]&&w){
ll MIN=min(maxf-ret,w);
w=dfs(v,MIN,t);
edge[i].w-=w;
edge[i^1].w+=w;
ret+=w;
if(ret==maxf)break;
}
}
if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了
return ret;
}
ll Dinic(ll s,ll t){
ll ans=0;
while(bfs(s,t)) ans+=dfs(s,INF,t);
return ans;
}
int main(){
cin>>m>>n;
init();
ll u,v;
while(cin>>u>>v){
if(u == -1 && v == -1) break;
add2(u,v,1,true);
}
for(ll i = 1;i <= m;++i)add2(0,i,1,true);
for(ll i = m+1;i <= n;++i)add2(i,n+1,1,true);
ll ans = Dinic(0,n+1);
cout<<ans<<endl;
if(ans == 0){
cout<<"No Solution!"<<endl;
return 0;
}
for(ll i = head[0];~i;i = edge[i].nxt){
if(edge[i].w == 0){
for(ll j = head[edge[i].to];~j;j = edge[j].nxt){
if(edge[j].w == 0){
cout<<edge[i].to<<' '<<edge[j].to<<endl;
}
}
}
}
return 0;
}