类似确定根的最小树型图的算法
1.对每个节点v都在所有{(u,v)}中选一条权最小的,连起来
2.判断有没有2个或者更多的有向环,有则类似的进行收缩,并修改G中边(和权),重复1
  如果只有1个则转3
3.计算费用

子集的性质a),b),c)保证算法肯定会结束并得到一个满足条件a),b),c)的一个节点数等于边数的子图

如果用等价类判断有没有环速度不慢
不过我不肯定这样的结果是否最优

• 有多个环的时候你收缩哪个？ (227) xreborner 2005-09-24 10:16:23
  • 都收缩 (0) atlas_of_rruucc 2005-09-24 11:29:36
    • 显然不正确啊 (0) xreborner 2005-09-24 12:18:18
      • 那你后来是怎么做的? (33) atlas_of_rruucc 2005-09-24 21:36:46