这是一个创建于 2925 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 30 名程序员，两两配对，结对编程 （分成 15 组）。
二维数组 profit[i][j] = k，表示程序员 i 和程序员 j 配对时的小组效率为 k，求使效率总和最大化时的最优配对。
对于任意 i != j, profit[i][j] == profit[j][i]
二维数组 profit[i][j] = k，表示程序员 i 和程序员 j 配对时的小组效率为 k，求使效率总和最大化时的最优配对。
对于任意 i != j, profit[i][j] == profit[j][i]
 | 1 karia 2017-10-15 20:04:58 +08:00 最大流 |
| 2 karia 2017-10-15 20:07:06 +08:00  1 [EK Algorithm]( https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm) |
| 5 karia 2017-10-15 20:11:41 +08:00 @mutelog 起点到 30 个人各有一条无限容量管道，30 个人到 30 个人的管道容量根据邻接矩阵建好，30 个人到终点各有一条无限容量管道 然后愉快模板 |
| 7 karia 2017-10-15 20:20:57 +08:00 好像是有点问题，我再想想 带权的二分图可能要用 KM 算法 |
| 8 karia 2017-10-15 20:28:28 +08:00 是的，最大流有问题，因为这条边的流量要么满，要么 0 https://en.wikipedia.org/wiki/Hungarian_algorithm KM 讲的是最小化问题，不过应该一样，大不了取负权 |
 | 9 XDXX 2017-10-15 21:57:27 +08:00 [Stable marriage problem]( https://en.wikipedia.org/wiki/Stable_marriage_problem) |
 | 10 mutelog OP @XDXX Stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. 这个是说两个等大小的集合互相匹配；但是题目里只有一个集合，集合里的任意两个元素都可以相互配对。 似乎不能用稳定结婚问题来解决 |
 | 11 allinwonder 2017-10-15 22:33:01 +08:00 via iPhone 2 @XDXX 这个完全不是一个 matching 的问题（我自己就是做 matching 研究的）。 要么穷举所有的配对可能然后找最大值，要么贪心算法找近似最优解。 这里应该有高手可能给你提供更好的剪枝方法的。 |
| 12 karia 2017-10-15 23:07:28 +08:00 |
 | 13 skadi 2017-10-16 00:09:03 +08:00 感觉似乎可以用 01 背包来解. 每个人只能用一次,然后有费用. |
 | 14 ytmsdy 2017-10-16 00:11:09 +08:00 via iPhone 做一个 BFS 就可以了。 把它简化为一个快递员要送 n 个包裹，要去 n 个地方，两两之间的耗时都给出，问你着么样的路径耗时最短？ 这个网上就一堆答案了！ |
 | 15 starqoq 2017-10-16 03:12:29 +08:00 via Android 3 |
| 16 mutelog OP @starqoq 感谢 找到一个题目 http://uoj.ac/problem/81 一般图最大权匹配 |
 | 17 resturlaub 2017-10-16 12:54:04 +08:00 匈牙利算法 |
Select Language