作者petingo (皮挺哥)
看板Prob_Solve
标题[问题] 给定一个无向图，求将节点两两分组的方式
时间Wed Apr 10 15:45:47 2024
大家早 :D
小弟日前遇到这个问题，想了几天还没想到暴力以外的做法
希望版上的大神可以出手相救
--
给定一个无向有权图，求将各个节点两两分组的方式
节点必须用完且每个节点只能用一次
所有组合方式或 iteration 的方法皆可
节点数量应该 < 50
举例来说
https://imgur.com/nm8kv4x.png
有三种组合方式：
1. (0, 4) (1, 5) (2, 3)，权重总和为 6
2. (0, 1) (2, 3) (4, 5)，权重总和为 11
3. (0, 5) (1, 4) (2, 3)，权重总合为 15
根据权重总和进行 iteration ，顺序会是先 1 -> 2 -> 3
先谢谢大家了
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 185.25.193.156 (瑞士)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1712735151.A.A6B.html
1F：推 LPH66: 也就是说, 对所有 perfect matching 依权重和列举出来这样? 04/10 19:18
对！原来这东西叫 perfect matching
我用这个关键字再搜寻看看
※ 编辑: petingo (185.25.193.156 瑞士), 04/10/2024 19:38:50
找到解法了
先建一张表纪录各点可以到达的比自己大的点（key 为起始点，value 为可到达的点）
以上面的例子来说，就是
0 -> 1, 2, 4, 5
1 -> 4, 5
2 -> 3, 4
4 -> 5
然後由小到大 iterate key，并维护一个阵列 combinations
储存至今为止所能形成的 match
每次 iteration 结束时，删除 combinations 中不包含当前 key 的 match
由於後续的迭代不会再出现 <= 当前 key 的值，因此该组合不可能为 perfect matching
不知道时间复杂度该怎麽算
但跑起来还算快（？
Python code:
https://gist.github.com/Petingo/f13bdd820e98a4dead3a36370b78b0b8
※ 编辑: petingo (185.25.193.156 瑞士), 04/12/2024 00:09:49
2F：→ FRAXIS: 不是应该用 Edmonds's matching algorithm 吗 04/12 03:49
我对 Edmond's matching algorithm 的理解是他只能找到其中的一组解？
但我需要所有可能的组合
维基百科说计算 perfect matching 的数量是
#P-complete，所以要找所有组合大概也只
能硬爆吧？
※ 编辑: petingo (185.25.193.156 瑞士), 04/12/2024 16:13:21
3F：→ FRAXIS: 如果要穷举的话大概就只能暴力解了.. 04/16 21:17