2 meditator hkx Meditator_hkx 于 2016.02.12 19:38 提问

Edmonds算法:最大权匹配的java实现 100C

最近帮忙做一个课题任务,要求用java实现Edmonds算法。
Edmonds算法的具体描述可以参阅百度文库的这篇文章:
http://wenku.baidu.com/link?url=GVU282p9OTXuMPlFUy4eb_a_j-t2TO8HsHEh-rzPo0_y6txgB6jCuNGwBfhhWA1i87mrInc31Z4pIGp1mPPCJGCwPKLOcfpvLqz7_7QnFmS

要求输入:图的节点和带权边
要求输出:边的最大匹配,用List表示

就算没有程序,只有思路也是欢迎的。
我自己的没有太多时间做这个,希望各位大神不吝赐教。

1个回答

caozhy
caozhy   Ds   Rxr 2016.02.12 21:46

here is an Edmonds algorithm implementation in java found on wikibooks
https://en.wikibooks.org/wiki/Algorithm_Implementation/Graphs/Maximum_flow/Edmonds-Karp

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
二分匹配总结(匈牙利算法+最大权+最小权)
转自:http://dingdongsheng.cool.blog.163.com/blog/static/1186187552009431405995/ 前段时间为了省赛,我专门花了半个月来“专研”二部图,目前对二部图还是有一点点心得,所以就记录下来,希望对某些人有用。   开始我对二部图一窍不通,于是就在网上找资料,认真看完了各种资料,有一种感触:关于最大匹配问题,网上写的是挺好的
Kuhn-Munkres算法(二分图最大权匹配)
Kuhn-Munkres算法(二分图最大权匹配) 这篇博客没有题,就是简单的说一下KM算法,今天花了两个小时学KM算法,总算明白了基本套路和基本原理,但是,有一个点从头到尾我都没有懂,lx[i]+ly[j]>weight[i][j]为什么是进入二分子图的条件,从百度上搜了也没有解释,GG了。还有就是这个式子求出来的值为何就是不合法匹配和合法匹配的最小差值,就这两个问题,一直搞不懂.....好迷啊
【POJ 2195】 Going Home(KM算法求最小权匹配)
【POJ 2195】 Going Home(KM算法求最小权匹配) Going Home Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 20303   Accepted: 10297 Description On a grid map there a
KM算法(完备匹配下的最大权匹配)
KM算法求的是完备匹配下的最大权匹配: 在一个二分图内,左顶点为X,右顶点为Y,现对于每组左右连接XiYj有权wij,求一种匹配使得所有wij的和最大。 题目:http://acm.hdu.edu.cn/showproblem.php?pid=2255 题意:分房子,对于n个人对n所房子有自己的最大承受价格,要求每个人分到一所房子,并且要求收入最大 输入说明:输入n,代表n个人和n所房子
二分图最大匹配及最大权匹配(km算法)
看过很多二分图匹配的ppt,感觉就这个说的最清楚了,是一个叫刘汝佳的人写的,百度搜了一下貌似挺牛逼的,不管那么多,对km算法还抓耳挠腮的同志可以看看这个。
Tour(二分图最大权匹配)(网络流)
题意:给你一个有向图,边有权值,现在要你求若干个环包含所有的顶点,并且每个顶点只出现一次(除了一个环中的起始点)使得华中所有边得权值之和最小。 像这杨构成圈并且每个点只能属于一个圈的题, 可以转化成2 分图, 每个点只能属于一个圈, 那么出度和入度必定为1 , 那么把一个点拆开i, i`, i控制入读, i` 控制出度, 流量只能为1 。 那么对于原来途中有的边 可以 i -
一般图最大匹配问题-带花树开花算法
以前用这个算法写过一两个水题,当时纯粹是套用模板,对算法本身是一知半解。然后Watashi的多校题中有个带花树模板题,现成的模板都套出了各种死循环,RE问题,弱爆了。这两天重新看了看论文和博客,重新理解了一遍,顺便把论文的前小半部分关于二分图最大匹配和一般图最大匹配的地方翻译了一下,论文的后半部分的二分图最大权匹配和一般图最大权匹配问题暂时还没看。 论文地址:http://builtinclz.
hdu 3395(费用流,二分图的最大权匹配)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3395 解题思路: 这个构图很容易出错,最开始都容易想,把每个点拆开,分为攻击和被攻击的,建图如下: 源点s与攻击的鱼i建边(s,i,1,0); 假设i攻击j,则建边(i,j+n,1,-val[i]^val[j]); 被攻击的鱼i与汇点建边(i+n,t,1,0); 但这个思路是错的,
最大权匹配KM算法的理解
如果m和n不相同时,最好把小的放上面,因为每次都是找上面一点的匹配点,找到满意的才会退出。若求最大权匹配,则匹配的点可以不存在(此时权值为0)。但如果求最小权匹配的话,直接把匹配的关系的权值取反的话,不存在的关系权值为0反而是最大的,所以就会出错。这时有两个解决方法,第一个就是保
二分图最佳完美匹配——Kuhn-Munkres算法 (最大权匹配)
二分图最大权匹配的代码: #include #include #include #include using namespace std; #define N 100 class Solution { public: int S[N]; int left[N]; // the id in left that matches an id in the right co