传送门：洛谷 - P2756
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
输入描述
第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1–m；英国飞行员编号为 m+1–n。
接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。
输出描述
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。
思路分析
建立源点s，汇点t，让1–m所有点与源点相连，m+1—n所有点与汇点相连，最大流就是最佳方案，判断反向边有无流量即可。
样例输入
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
样例输出
4
1 7
2 9
3 8
5 10
AC代码
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define int long long
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=1e5+10;
struct node{
int v,w,next;
}e[N];
int head[N],cnt;
int n,m,s,t,dep[N];
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs(){
queue<int>q;
mem(dep,0);
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
int w=e[i].w;
if(w && !dep[v]){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int f){
if(u==t)
return f;
int fl=0;
for(int i=head[u];i&&f;i=e[i].next){
int v=e[i].v;
if(dep[v]==dep[u]+1 && e[i].w){
int nx=dfs(v,min(f,e[i].w));
e[i].w-=nx;
e[i^1].w+=nx;
f-=nx;
fl+=nx;
}
}
if(!fl)
dep[u]=-2;
return fl;
}
int dinic(){
int ans=0;
while(bfs())
ans+=dfs(s,INF);
return ans;
}
signed main() {
IOS;
#ifdef xiaofan
freopen("in.txt","r",stdin);
#endif
cin>>m>>n;
cnt=1;
s=0,t=n+1;
int a,b;
while(cin>>a>>b){
if(a==-1 && b==-1)
break;
add(a,b,INF);
add(b,a,0);
}
for(int i=1;i<=m;i++){
add(s,i,1);
add(i,s,0);
}
for(int i=m+1;i<=n;i++){
add(i,t,1);
add(t,i,0);
}
int ans=dinic();
if(!ans){
cout<<"No Solution"<<endl;
return 0;
}
cout<<ans<<endl;
for(int i=2;i<=cnt;i+=2){
if(e[i].v==s||e[i^1].v==t)
continue;
if(e[i].v==t||e[i^1].v==s)
continue;
if(e[i^1].w)
cout<<e[i^1].v<<" "<<e[i].v<<endl;
}
return 0;
}
