二分图最大匹配

2019-11-11 02:56:20

字体：大中小

来源：转载

供稿：网友

学了匈牙利算法（时间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); PRintf("%d/n",n-ans); }}

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;}

上一篇：.Net 中的反射(查看基本类型信息)

下一篇：C#学习日记2017-02-07 Combox下拉控件问题