题目大意:给定一个无向图,判断它的最小生成树是否唯一。
输入:
第一行:测试数据的组数t(1<=t<=20)
每组测试数据的第一行:顶点数n(1<=n<=100),边数m
每组测试数据的后面m行:顶点x,顶点y,边长w
输出:
最小生成数唯一:输出构成最小生成树的边的和
最小生成数不唯一:输出Not Unique!
解题思路:
1.先找出最小生成树的一组边的组合,然后依次去掉该最小生成树边的组合中的一条边,然后再做最小生成树。判断后面生成的最小生成数边的和是否和第一次生成的最小生成树边的和相等,如果有一个相等就说明最小生成树不唯一。当所有的边都被去掉一次之后还没有出现边的和相等的情况,就说明最小生成树唯一
2.测试数据中有0的边。这个是很重要的,用prim或者kruskal的时候都要做这个判断。否则就会出错,如下面一组数据:
4 4
1 2 4
2 3 0
3 4 4
如果不对0的边处理的话输出的会是Not Unique! 因为按照普通最小生成树的做法。(2,3)这条边是会出现在第一次生成的最小生成树的边序列里面的,当去掉(2,3)这条边是,生成的最小生成树的大小没有影响,而2 3 0本身的意思是2和3重合。所以判断就出错了。
3.对于边长为0的边我想了很多种处理方法,比较好的就是第一次生成最小生成树的时候为0的边就不加到边的序列里面。从而后面的操作也就不会受到影响了。(但是让我惊奇的是我以前用prim做的时候竟然是直接判断如果出现了0的边那它就肯定是唯一的。结果也ac了,所以poj的测试数据应该也是有点问题的。)
下面一组就有0而且是不唯一的
1 2 2
2 3 0
3 4 2
1 4 2

发表评论

电子邮件地址不会被公开。

Post Navigation