HDU 1083 Courses 匈牙利算法模板题 发表于 2017-05-15 | 分类于 算法 | 阅读次数: 字数统计: 498 字 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1083 题意&题解给出一个二分图求最大匹配个数,判断时候和一边的数相等,以此题当做匈牙利算法模板 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<ctime>#include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 0x3f3f3f3fconst int maxn=1000;const int maxm=100005; /* ************************************************************************** //二分图匹配(匈牙利算法的DFS实现) //初始化:g[][]两边顶点的划分情况 //建立g[i][j]表示i->j的有向边就可以了,是左边向右边的匹配 //g没有边相连则初始化为0 //L是匹配左边的顶点数,R是匹配右边的顶点数 //调用:res=hungary();输出最大匹配数 //优点:适用于稠密图,DFS找增广路,实现简洁易于理解 //时间复杂度:O(VE) // ***************************************************************************/ //顶点编号从1开始的 int LN,RN;//L,R数目 int g[maxn][maxn], linker[maxn]; //所连得边直接从做到右bool used[maxn]; int dfs(int L)//从左边开始找增广路径 { int R; for(R = 1; R <= RN; R++) { if(g[L][R]!=0 && !used[R]) { //找增广路,反向 used[R]=true; if(linker[R] == -1 || dfs(linker[R])) { linker[R]=L; return 1; } } } return 0;//这个不要忘了,经常忘记这句 } int hungary() { int res = 0 ; int L; memset(linker,-1,sizeof(linker)); for( L = 1; L <= LN; L++) { memset(used,0,sizeof(used)); if(dfs(L) != 0) res++; } return res; } void solve(){ int t; scanf("%d",&t); while(t--) { scanf("%d %d",&LN,&RN); int num,tmp; memset(g,0,sizeof(g)); for(int i=1;i<=LN;i++) { scanf("%d",&num); for(int j=0;j<num;j++) { scanf("%d",&tmp); g[i][tmp]=1; } } int ans=hungary(); if(ans==LN) printf("YES\n"); else printf("NO\n"); }}int main(){ freopen("input.txt","r",stdin); solve(); return 0;} 赏 WeChat Pay Alipay 本文作者: Sixzeroo 本文链接: https://www.liuin.cn/2017/05/15/HDU-1083-Courses-匈牙利算法模板题/ 发布时间: 2017年5月15日 - 21时05分 最后更新: 2019年1月27日 - 10时01分 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!