正題

鏈接：
https://www.luogu.org/record/show?rid=7921243

---

大意

就是有n個飛行員，m個外籍的，然后皇家的和外籍的配對求最大匹配

---

解題思路

裸網(wǎng)絡(luò)流二分匹配。
建圖：
源點S連向左邊的點，右邊點連匯點E，然后之間連接，所以的邊容量都是1

---

代碼

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct line{int to,next,w; }a[100010]; int n,m,x,y,d[110],tot,state[110]; int head,tail,ls[110],s,e,ans; void addl(int x,int y,int w) {a[tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot++;a[tot].to=x;a[tot].next=ls[y];a[tot].w=0;ls[y]=tot++; } bool bfs()//在殘量網(wǎng)上建立分層圖 {head=0;tail=1;memset(d,-1,sizeof(d));d[s]=0;state[1]=s;do{head++;int x=state[head];for (int q=ls[x];q;q=a[q].next){int y=a[q].to;if (a[q].w>0 && d[y]==-1){d[y]=d[x]+1;state[++tail]=y;if (y==e) return true;//可以到達(dá)}}}while (head<tail);return false;//不可以到達(dá)匯點了 } int dinic(int x,int flow) {int rest=0,k;if (x==e) return flow;for (int q=ls[x];q;q=a[q].next){int y=a[q].to;if (a[q].w>0 && d[y]==d[x]+1){rest+=(k=dinic(y,min(a[q].w,flow-rest)));//記錄流量a[q].w-=k;//減去剩余容量a[q^1].w+=k;//反向加上流量}}if (!rest) d[x]=0;//剪枝return rest; } int main() {scanf("%d%d",&n,&m);s=m+1;e=m+2;while (1){scanf("%d%d",&x,&y);if (x==-1 && y==-1) break;addl(x,y,1);//連接}for (int i=1;i<=n;i++) addl(s,i,1);for (int i=n+1;i<=m;i++) addl(i,e,1);while (bfs()) ans+=dinic(s,1e9);if (ans==0){printf("No Solution!");return 0;}printf("%d\n",ans);for (int i=0;i<tot;i+=2){if (a[i].to!=s&&a[i^1].to!=s&&a[i].to!=e&&a[i^1].to!=e)//判斷是在中間用于匹配的邊if (a[i^1].w!=0)//有流過的printf("%d %d\n",a[i^1].to,a[i].to);//輸出} }

總結(jié)

以上是生活随笔為你收集整理的P2756,ssl2601-飞行员配对问题【网络流24题,最大匹配,dinic】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。