文章目錄

• 題目描述
• 解析
• 代碼

題目描述

有n個點和m條邊的有向無環圖，在這張圖上的某些點上空投傘兵，使傘兵可以走到圖上所有的點。
且每個點只能被一個傘兵走一次。問至少需要放多少傘兵。

解析

考慮一開始給每個點分配一個傘兵，最差就是這樣n個傘兵的情況
然后就是考慮如何減少傘兵
因為不可重，所以每個點只能與一個入度和一個出度合并
考慮把每個點割成入點和出點，就變成了二分圖最大匹配問題
直接匈牙利或網絡流即可

代碼

#include<bits/stdc++.h> using namespace std; const int N=305; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,l; struct node{int from,to,nxt; }p[N*N*4]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){x,y,fi[x]};fi[x]=cnt; } int vis[N],mat[N]; bool dfs(int x,int tim){if(vis[x]==tim) return false;vis[x]=tim;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]=x;return true;}}return false; } int hungary(){int res=0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(mat));for(int i=1;i<=n;i++){if(dfs(i,i)){res++;//printf(" ok:%d\n",i);}}return res; } bool mp[155][155]; int main(){int T=read();while(T--){memset(fi,-1,sizeof(fi));cnt=-1;memset(mp,0,sizeof(mp));n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read();mp[x][y]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]) addline(i+n,j),addline(j,i+n);} }int res=hungary();printf("%d\n",n-res);}return 0; } /**/

總結

以上是生活随笔為你收集整理的YBTOJ：伞兵空降（二分图匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。