poj 1679 The Unique MST (判断mst的唯一性,次小生成树)

poj1679

题意:问最小生成树是否唯一。。

思路:求一下次小生成树。。。如果无解,或者次小生成树的权值之和和最小生成树的权值之和不同,那么唯一,否则不唯一。1A

 

ural 1416. Confidential (次小生成树模板题)

URAL1416
题意:次小生成树模板题

思路:用Kruskal求最小生成树,标记用过的边。求次小生成树时,依次枚举用过的边,将其去除后再求最小生成树,得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

 

写的时候。。因为点数是5[……]

Read more