> 给你一个测试数据：
> 6 5
> 1 6 98
> 2 3 94
> 2 4 13
> 2 6 52
> 5 6 81
> 0
> 如果没错的话，答案应该是676


看到带状态压缩的就头疼,,,KM我不会,,,于是选择了费用流,,,

结果这组数据就过不了,,发现原因是带权图的匹配对于对称的数据也未必会对称的连边,,这点和最大匹配很不一样,,而做这个题显然期望它对称连边,,,

我的费用流连边情况,,,将残留的度数为奇数的点拆开,分为2组,,源点和左边的一组连边,流量1,费用0,,汇点和右边的一组连边,流量1,费用0,,左边和右边的连边,,流量1,费用最短距离,,
,然后我输出了费用流的连边的情况,,发现是这样的,,1->6',,,2->3',,,3->4',,,4->2',,5->1',,,6->5',,,这显然是不对称的,,所以是错误的,,,

估计用KM也是类似的情况,,希望能那些WA的一些提示,,,换方法吧,,,我去研究dp了,,,

• Re:感谢这位大牛的数据,,,,,原来似乎不能用费用流或者KM来算,,, (376) zcube 2012-07-27 09:32:58
  • Re:感谢这位大牛的数据,,,,,原来似乎不能用费用流或者KM来算,,, (2) zcube 2012-07-27 09:34:18