[算法题] 结对编程最优配对问题

[mutelog]

有 30 名程序员，两两配对，结对编程 （分成 15 组）。

二维数组 profit[i][j] = k，表示程序员 i 和程序员 j 配对时的小组效率为 k，求使效率总和最大化时的最优配对。

对于任意 i != j, profit[i][j] == profit[j][i]

[karia]

最大流

[karia]

[EK Algorithm]( https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)

[mutelog]

@karia 能否更详细地描述下

[mutelog]

@karia 感谢，可否描述下怎么建图

[karia]

@mutelog 起点到 30 个人各有一条无限容量管道，30 个人到 30 个人的管道容量根据邻接矩阵建好，30 个人到终点各有一条无限容量管道
然后愉快模板

[mutelog]

@karia 这样建图恐怕不对吧，有可能出现 i 和 j 匹配，而 j 不和 i 匹配的情况

[karia]

好像是有点问题，我再想想
带权的二分图可能要用 KM 算法

[karia]

是的，最大流有问题，因为这条边的流量要么满，要么 0
https://en.wikipedia.org/wiki/Hungarian_algorithm
KM 讲的是最小化问题，不过应该一样，大不了取负权

[XDXX]

[Stable marriage problem]( https://en.wikipedia.org/wiki/Stable_marriage_problem)

[mutelog]

@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.
这个是说两个等大小的集合互相匹配；但是题目里只有一个集合，集合里的任意两个元素都可以相互配对。
似乎不能用稳定结婚问题来解决

[allinwonder]

@XDXX 这个完全不是一个 matching 的问题（我自己就是做 matching 研究的）。

要么穷举所有的配对可能然后找最大值，要么贪心算法找近似最优解。

这里应该有高手可能给你提供更好的剪枝方法的。

[karia]

@allinwonder 意识到问题了 :(
一旦掉坑里就很容易江化，最大流解决不了 A 配 B 时 B 也一定要配 A 的约束
等 dalao 了

[skadi]

感觉似乎可以用 01 背包来解.

每个人只能用一次,然后有费用.

[ytmsdy]

做一个 BFS 就可以了。
把它简化为一个快递员要送 n 个包裹，要去 n 个地方，两两之间的耗时都给出，问你着么样的路径耗时最短？
这个网上就一堆答案了！

[starqoq]

一般图最优匹配 带花树算法。搜论文
Efficient Algorithms for Finding Maximal Matching in Graphs

@karia 二分图都不对，任意两个程序员都能匹配，而不是说男的和女的匹配。

@ytmsdy 这不是旅行商问题

[mutelog]

@starqoq 感谢 找到一个题目 http://uoj.ac/problem/81 一般图最大权匹配

[resturlaub]

匈牙利算法