首页 > 代码库 > 二分图
二分图
二分图匹配
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
一般使用最大流或是匈牙利算法，我个人倾向于最大流，因为跑得更快，而且不必多背板子（尽管只有8行）。
例题：【模板】二分图匹配
匈牙利算法
1 #include<cstdio> 2 #include<cstring> 3 int n,m,k,ans; 4 int a,b,c; 5 int cp[1010]; 6 bool v[1010]; 7 int h[1010],hs; 8 struct edge{int s,n;}e[1000010]; 9 bool Hungarian_algorithm(int k){10 for(int i=h[k];i;i=e[i].n) if(!v[e[i].s]){11 v[e[i].s]=1;12 if(!cp[e[i].s]||Hungarian_algorithm(cp[e[i].s])){13 cp[e[i].s]=k;14 return true;15 }16 }17 return false;18 }19 int main(){20 scanf("%d%d%d",&n,&m,&k);21 for(int i=1;i<=k;i++){22 scanf("%d%d",&a,&b);23 if(a>0&&a<=n&&b>0&&b<=m)24 e[++hs]=(edge){b,h[a]},h[a]=hs;25 }26 for(int i=1;i<=n;i++){27 memset(v,0,sizeof(v));28 if(Hungarian_algorithm(i)) ans++;29 }30 printf("%d\n",ans);31 return 0;32 }
二分图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。