题解 P2756 【飞行员配对方案问题】
Creeper_LKF
2017-07-21 10:13:42
其实也可以用网络流做，但是网络流要比匈牙利算法慢上许多，但如果每两个匹配的飞行员有权值的话KM算法就很难写了
```cpp
#include<bits/stdc++.h>
#define INF 536870912
using namespace std;
int m,n,s,t;
int matrix[250][250],dis[250],cur[250];//邻接矩阵
namespace Dinic{//Dinic的标准套路+优化，用邻接矩阵写更清爽。其中matrix数组的功能很强大，可以检查连边，储存残量网络，正向边反向边通吃，免初始化......（赶紧拥有吧（滑稽））
inline bool BFS(){
queue<int> mession;
memset(dis,-1,sizeof(dis));
mession.push(s);
dis[s]=0;
int now;
while(!mession.empty()){
now=mession.front(),mession.pop();
for(int i=s;i<=t;i++){
if(dis[i]<0&&matrix[now][i]>0){//如果这个点没有被计算过分层且存在这条连边且残量>)
dis[i]=dis[now]+1;
mession.push(i);
}
}
}
if(dis[t]>0) return true;
return false;//这个时候到终点已经没有可增广的流量了
}
inline int DFS(int depth,int f){
if(depth==t||f==0) return f;//不知名的优化，却很有用
for(int &i=cur[depth];i<=t;i++){//当前弧优化
int ns=0;
if(matrix[depth][i]>0&&dis[i]==dis[depth]+1&&(ns=DFS(i,min(f,matrix[depth][i])))){//如果连边且残量>0且满足层数要求且可以增广
matrix[depth][i]-=ns;//增广
matrix[i][depth]+=ns;
return ns;
}
}
return 0;
}
inline int dinic(){
int ans=0,ns;
while(BFS()){
memset(cur,s,sizeof(cur));
while((ns=DFS(s,INF))&&(ans+=ns));
}
return ans;
}
}
namespace IN{
inline int read(){
int num=0;
char c;
while(isspace(c=getchar()));
if(c=='-') return -1;//判断结束（这个读入优化很灵活）
while((num=num*10+c-48)&&isdigit(c=getchar()));
return num;
}
inline void init(){
m=read(),n=read(),s=0,t=m+n+1;
int x,y;
while((x=read())!=-1&&(y=read())){
matrix[x][y]=INF;//允许本地飞行员到外籍飞行员的连边（取INF是为了保证流量流通），同时检测是否有流量连向两飞行员
matrix[s][x]=matrix[y][t]=1;//建立每一本地飞行员到超级源点和外籍飞行员到超级汇点，容量为1（可以理解成每一个人只能与一人配对）
}
}
}
int main(){
IN::init();
printf("%d\n",Dinic::dinic());
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(matrix[i][j])//如果逆向边有流量则两点连边
printf("%d %d\n",j,i);
return 0;
}
```