> 类似确定根的最小树型图的算法
> 1.对每个节点v都在所有{(u,v)}中选一条权最小的,连起来
> 2.判断有没有2个或者更多的有向环,有则类似的进行收缩,并修改G中边(和权),重复1
>   如果只有1个则转3
> 3.计算费用
> 
> 子集的性质a),b),c)保证算法肯定会结束并得到一个满足条件a),b),c)的一个节点数等于边数的子图
> 
> 如果用等价类判断有没有环速度不慢
> 不过我不肯定这样的结果是否最优

• 都收缩 (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