C语言[二分图最大匹配] 匈牙利算法
发布时间:2020-12-16 07:44:05 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 const int INF = 0x3f3f3f3f;const int MAXN=510;int uN,vN;//u,v数目int g[MAXN][MAXN];//构图int link[MAXN]; //link[v]=u表示右边对左边的匹配bool
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 const int INF = 0x3f3f3f3f; const int MAXN=510; int uN,vN;//u,v数目 int g[MAXN][MAXN];//构图 int link[MAXN]; //link[v]=u表示右边对左边的匹配 bool used[MAXN];//是否访问过 bool dfs(int u)//从左边开始找增广路径 { int v; for(v=0;v<vN;v++)//右边顶点编号从0开始 { if(g[u][v]&&!used[v]) //如果存在通路,且从u开始搜索时该点没访问过 { used[v]=true; if(link[v]==-1 || dfs(link[v])) //找增广路 { link[v]=u; return true; } } } return false; } int hungary() { int res=0; int i,u; memset(link,-1,sizeof(link)); for(u=0;u<uN;u++) { memset(used,sizeof(used)); if(dfs(u)) res++; } return res; } 以上是匈牙利算法的关键代码 其实实现就是一个找增广路径的过程 增广路径?字面意思就是把路径越增越广 实际意思也是一样的 DFS从左边起始点开始搜索 1.右边如果没匹配就匹配(link[v]==-1) 2.如果右边匹配过了...就从右边点找左边的匹配点再搜索看是否能增广 以上两种情况都能使匹配边+1 这就是找二分图最大匹配的最简单算法了,代码很短,时间复杂度为O(n^3),网络流当然也能实现咯... 记住咯:? 最小点覆盖?=?二分图最大匹配 最小路径覆盖?=?|P|?-?二分图最大匹配 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |