二分圖最大匹配

2019-11-11 01:40:58

字體：大中小

來源：轉載

供稿：網友

學了匈牙利算法（時間O(nm)），練幾道板子……

POJ1422 將一個點拆成兩個，分別加入到X,Y集合中，對于一條有向邊u->v建一條邊：X中的u指向Y中的v。假設先把n個頂點布滿傘兵，每有一組匹配就可以少一個傘兵，所以最小傘兵數=n-最大匹配數。上代碼：

//POJ1422 拆點+二分圖匹配 #include <cstdio>#include <algorithm>#include <cstring>#define maxn 121using namespace std;int ans,T,m,n,x,num,y,head[maxn],vis[maxn],match[maxn];struct xx{ int v,next;}b[maxn*maxn];void add(int u,int v){ b[++num]=(xx){v,head[u]}; head[u]=num;}int dfs(int t){ int v,k; for (k=head[t],v=b[k].v;k!=0;k=b[k].next,v=b[k].v) if (!vis[v]) { vis[v]=1; if (!match[v]||dfs(match[v])) { match[v]=t; return true; } } return false;}int main(){ scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); num=ans=0; memset(match,0,sizeof(match)); memset(head,0,sizeof(head)); for (int i=0;i<m;i++) scanf("%d%d",&x,&y),add(x,y); for (int i=1;i<=n;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i); POJ1325

//POJ1325 二分圖匹配最小覆蓋=最大匹配 #include <cstdio>#include <cstring>#include <algorithm>#define maxn 105using namespace std;int n,m,num,k,head[maxn],vis[maxn],ans,x,y,z,match[maxn];struct xx{ int v,next;}b[1005];void add(int u,int v){ b[++num]=(xx){v,head[u]}; head[u]=num;}int dfs(int t){ for (int k=head[t];k!=0;k=b[k].next) { int v=b[k].v; if (!vis[v]) { vis[v]=1; if (!match[v]||dfs(match[v])) { match[v]=t; return true; } } } return false;}int main(){ while (scanf("%d%d%d",&n,&m,&k)==3) { num=ans=0; memset(head,0,sizeof(head)); memset(match,0,sizeof(match)); for (int i=0;i<k;i++) { scanf("%d%d%d",&x,&y,&z); if (y*z)add(y,z); } for (int i=0;i<n;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i); printf("%d/n",ans); }}

POJ1466 由于性別有男女兩種（特殊情況不予考慮），最大匹配會算兩次，所以答案=最大獨立集=節點數-最大匹配/2 (因為覆蓋集（每條邊至少有一個點被選中）和獨立集（每條邊至少有一個點不被選中）的概念恰好相反，so最小覆蓋集和最大獨立集“互補”)

//POJ1466 二分圖匹配 #include <cstdio>#include <cstring>#include <algorithm>#define maxn 505using namespace std;int n,x,y,z,m,vis[maxn],num,ans,head[maxn],match[maxn];struct xx{ int v,next;}b[maxn*maxn<<2];void add(int u,int v){ b[++num]=(xx){v,head[u]}; head[u]=num;}int dfs(int t){ for (int k=head[t];k!=0;k=b[k].next) { int v=b[k].v; if (!vis[v]) { vis[v]=1; if (match[v]==-1||dfs(match[v])) { match[v]=t; return true; } } } return false;}int main(){ while (scanf("%d",&n)==1) { num=ans=0; memset(head,0,sizeof(head)); memset(match,-1,sizeof(match)); for (int i=0;i<n;i++) { scanf("%d: (%d)",&x,&m); for (int j=0;j<m;j++) scanf("%d",&y),add(i,y),add(y,i); } for (int i=0;i<n;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i); printf("%d/n",n-(ans>>1)); } return 0;}