这是一个创建于 2600 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 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