hdu 题目2063 过山车(二分图匹配,匈牙利算法)

发布时间:2016-12-8 19:56:27 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 题目2063 过山车(二分图匹配,匈牙利算法)",主要涉及到hdu 题目2063 过山车(二分图匹配,匈牙利算法)方面的内容,对于hdu 题目2063 过山车(二分图匹配,匈牙利算法)感兴趣的同学可以参考一下。

http://acm.hdu.edu.cn/showproblem.php?pid=2063 简单的二分图匹配 注意: 1.邻接矩阵G必须初始化 2.当搜索时,i如果已经匹配,再寻找增广路时是 dfs(link[ i ]); /*************************** # 2013-9-3 7:30:23 # Time: 15MS Memory: 484K # Author: zyh # Status: Accepted ***************************/ #include<stdio.h> #include<string.h> int m,n; bool G[510][510],vis[510]; int link[510]; bool dfs(int x){ for(int i=1;i<=n;i++){ if(G[x][i] && !vis[i]){ vis[i]=1; if(link[i]==-1 || dfs(link[i])){ link[i] = x; return 1; } } } return 0; } int main() { int k,i,sum,x,y; while(scanf("%d",&k),k) { scanf("%d%d",&m,&n); memset(link,-1,sizeof(link)); memset(G,0,sizeof(G)); //!!!每次必须初始化G for(i=0;i<k;i++){ scanf("%d%d",&x,&y); G[x][y] = 1; } for(sum=0,i=1;i<=m;i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) sum++; } printf("%d\n",sum); } return 0; }

上一篇:
下一篇:魅族新机MX3体验

相关文章

相关评论