6187专题

Destroy Walls HDU - 6187(最大生成树)

Destroy Walls 题目链接:HDU - 6187 题意:现有一个图,一个人在图中某一点,要使此人能够达到任意位置,需要拆掉的边最少且付费代价最少是多少; 思路:如果想到达任意位置,那么图中一定无环,首先想到的是拓扑排序判环,然后将每个环中的最小边去掉,但是这样太复杂了,,,换个方向,,,图中无环不就是全是树嘛!要求代价最小,那么构造一个最大生成树(森林)就OK了 ;