【学术篇】网络流24题--飞行员配对方案问题

2019-11-06 08:05:37

字体：大中小

来源：转载

供稿：网友

咳咳…… 传送门：https://daniu.luogu.org/PRoblem/show?pid=2756

这个题的基本模型：二分图最大匹配。。我们可以将外籍飞行员放在左边，英国飞行员放在右边，能合作的两个飞行员之间连一条边，构出来的图就像这样~~ 图片以样例为例

这样能派出的最大飞机数就是这个二分图的最大匹配…… 最简单的算法是Hungary Algorithm（匈牙利算法）~~（并不是Hungry）~~

匈牙利算法比较简单，你们自己去搜一下，原理代码都很清楚。。不过令我吐槽的是搜到的模板基本都是邻接矩阵写的，而我比较习惯数组模拟的邻接表 _ (:з」∠) _

然后下面是代码（时间复杂度：O(N^2*M)）

#include <cstdio>#include <cstring> #define gc getchar()#define cl(a,b) memset(a,b,sizeof(a))const int N=505;struct edge{ int to,next;}e[N*N+15]; int v[N],tot=1;int c[N],match[N];bool vis[N];int n,m;inline int gnum(){ int a=0;char c=gc;bool f=0; for(;(c<'0'||c>'9')&&c!='-';c=gc); if(c=='-') f=1,c=gc; for(;c>='0'&&c<='9';c=gc) a=(a<<1)+(a<<3)+c-'0'; if(f) return -a; return a;}void build(int x,int y){ e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;}bool dfs(int x){ for(int i=v[x];i;i=e[i].next){ int y=e[i].to; if(vis[y]==0){ vis[y]=1; if(match[y]<0||dfs(match[y])){ c[x]=y; match[y]=x; return 1; } } } return 0;}int hungary(){ int ans=0; for(int i=1;i<=m;i++) if(c[i]<0) cl(vis,0),ans+=dfs(i); return ans;}int main(){ n=gnum(),m=gnum(); cl(match,-1); cl(c,-1); do{ int u=gnum(),v=gnum(); if(u==-1) break; build(u,v); }while(1); int ans=hungary(); if(!ans){ puts("No Solution!"); return 0; } printf("%d/n",ans); for(int i=1;i<=m;i++) //输出方案.. if(~c[i]) printf("%d %d/n",i,c[i]);}

不过，二分图上还N^2*M的算法怎能忍受.. 所以，两位歪果大神YY出了一种O(N^0.5*M)的算法.. 他们一个人叫John E. Hopcroft，另一个叫Richard M. Karp，所以这个算法叫Hopcroft-Karp算法.. 这个算法网上讲的也不少，但模板似乎竟然还有假的..（比如这题样例都会找错）还有神犇想要具体研究这个算法可以去看原始论文其实是可以下到的~~ 论文你们可以去http://download.csdn.net/detail/shoulea/5659515 下嘛..

代码：

#include <queue>#include <cstdio>#include <cstring>using std::queue;#define gc getchar()#define cl(a,b) memset(a,b,sizeof(a))const int N=505;const int INF=~0U>>1;int cx[N],cy[N],dx[N],dy[N];bool vis[N];int n,m,dis;struct Node{ int to,next;}e[N*N+15]; int v[N],tot=1;inline int gnum(){ int a=0;char c=gc;bool f=0; for(;(c<'0'||c>'9')&&c!='-';c=gc); if(c=='-') f=1,c=gc; for(;c>='0'&&c<='9';c=gc) a=(a<<1)+(a<<3)+c-'0'; if(f) return -a; return a;}inline void build(int x,int y){ e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;}bool bfs(){ cl(dx,-1); cl(dy,-1); queue<int> q; dis=INF; for(int i=1;i<=m;i++) if(cx[i]<0) q.push(i),dx[i]=0; while(!q.empty()){ int x=q.front(); q.pop(); if(dx[x]>dis) break; for(int i=v[x];i;i=e[i].next){ int y=e[i].to; if(dy[y]<0){ dy[y]=dx[x]+1; if(cy[y]<0) dis=dy[y]; else dx[cy[y]]=dy[y]+1,q.push(cy[y]); } } } return dis!=INF;}bool dfs(int x){ for(int i=v[x];i;i=e[i].next){ int y=e[i].to; if(!vis[y]&&dy[y]==dx[x]+1){ vis[y]=1; if(cy[y]!=-1&&dy[y]==dis) continue; if(cy[y]==-1||dfs(cy[y])){ cx[x]=y; cy[y]=x; return 1; } } } return 0;}int hopcroft_karp(){ int ans=0; cl(cx,-1); cl(cy,-1); while(bfs()){ cl(vis,0); for(int i=1;i<=m;i++) if(cx[i]<0&&dfs(i)) ans++; } return ans;}int main(){ n=gnum(); m=gnum(); do{ int u=gnum(),v=gnum(); if(u==-1) break; build(u,v); }while(1); int ans=hopcroft_karp(); if(!ans){ puts("No Solution!"); return 0; } printf("%d/n",ans); for(int i=1;i<=m;i++) if(~cx[i])printf("%d %d/n",i,cx[i]);}

这样就结束了吗？并不是的，这题还有更一般的做法——网络流。。 ~~不然干嘛要归到网络流24题里啊~~ 我们搞出一个源点S和汇点T，将所有外籍飞行员与S连边，将所有英国飞行员与T连边，我们再看：这里写图片描述

这就是一个网络流图了。。因为是二分图，我们不妨跑dinic（其实还是O(N^0.5*M)）不过拥有更好的普适性~~而且还能直接复制粘贴板子~~ 代码：

#include <queue>#include <cstdio>#include <cstring>using std::queue;using std::min;#define gc getchar()#define cl(a,b) memset(a,b,sizeof(a))const int MAXV=202;const int MAXE=40404;const int INF=~0U>>1;struct edge{ int to,next,data;}e[MAXE]; int v[MAXV],tot=1;int d[MAXV];int cur[MAXV];int s,t;inline int gnum(){ int a=0; char c=gc; bool f=0; for(;(c<'0'||c>'9')&&c!='-';c=gc); if(c=='-') f=1,c=gc; for(;c>='0'&&c<='9';c=gc) a=(a<<1)+(a<<3)+c-'0'; if(f) return -a; return a;}void build(int x,int y,int z){ e[++tot].to=y; e[tot].next=v[x]; e[tot].data=z; v[x]=tot; e[++tot].to=x; e[tot].next=v[y]; e[tot].data=0; v[y]=tot;}bool bfs(){ cl(d,-1); d[s]=0; for(int i=s;i<=t;i++) cur[i]=v[i]; queue<int> q; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=v[x];i;i=e[i].next) if(e[i].data&&d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to); } return d[t]>0;}int dfs(int x,int mx){ if(!mx||x==t) return mx; int k,s=0; for(int i=cur[x];i;i=e[i].next){ cur[x]=i; if(d[e[i].to]==d[x]+1&&(k=dfs(e[i].to,min(mx,e[i].data)))){ s+=k; mx-=k; e[i].data-=k; e[i^1].data+=k; if(!mx) break; } } return s;}int dinic(){ int ans=0; while(bfs()) ans+=dfs(s,INF); return ans;}void findpath(int m){ for(int x=1;x<=m;x++) for(int i=v[x];i;i=e[i].next) if(!(i&1)&&!e[i].data) printf("%d %d/n",x,e[i].to); }int main(){ int m=gnum(),n=gnum(),ans; s=0,t=n+1; for(int i=1;i<=m;i++) build(s,i,1); for(int i=m+1;i<=n;i++) build(i,t,1); do{ int u=gnum(),v=gnum(); if(u==-1) break; build(u,v,1); }while(1); ans=dinic(); if(!ans) puts("No Solution!"); else printf("%d/n",ans),findpath(m);}

最后的最后，我要告诉大家一个秘密^o^：这题没有No Solutiontion的情况~~ ~~我会说我已经用两种代码A完才看见无解要输出No Solution嘛~~

The End..

上一篇：网易短网址转换

下一篇：似然函数（Likelihood function）是什么