这是一个创建于 3033 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 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 日 最大流 |
| 2 karia 2017 年 10 月 15 日  1 [EK Algorithm]( https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm) |
| 5 karia 2017 年 10 月 15 日 @mutelog 起点到 30 个人各有一条无限容量管道，30 个人到 30 个人的管道容量根据邻接矩阵建好，30 个人到终点各有一条无限容量管道 然后愉快模板 |
| 7 karia 2017 年 10 月 15 日 好像是有点问题，我再想想 带权的二分图可能要用 KM 算法 |
| 8 karia 2017 年 10 月 15 日 是的，最大流有问题，因为这条边的流量要么满，要么 0 https://en.wikipedia.org/wiki/Hungarian_algorithm KM 讲的是最小化问题，不过应该一样，大不了取负权 |
 | 9 XDXX 2017 年 10 月 15 日 [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 日 via iPhone 2 @XDXX 这个完全不是一个 matching 的问题（我自己就是做 matching 研究的）。 要么穷举所有的配对可能然后找最大值，要么贪心算法找近似最优解。 这里应该有高手可能给你提供更好的剪枝方法的。 |
| 12 karia 2017 年 10 月 15 日 |
 | 13 skadi 2017 年 10 月 16 日 感觉似乎可以用 01 背包来解. 每个人只能用一次,然后有费用. |
 | 14 ytmsdy 2017 年 10 月 16 日 via iPhone 做一个 BFS 就可以了。 把它简化为一个快递员要送 n 个包裹，要去 n 个地方，两两之间的耗时都给出，问你着么样的路径耗时最短？ 这个网上就一堆答案了！ |
 | 15 starqoq 2017 年 10 月 16 日 via Android 3 |
| 16 mutelog OP @starqoq 感谢 找到一个题目 http://uoj.ac/problem/81 一般图最大权匹配 |
 | 17 resturlaub 2017 年 10 月 16 日 匈牙利算法 |
Select Language