首页 > 代码库 > Unique MST

Unique MST

2024-07-03 06:39:54   225人阅读

Unique MST

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree):

Consider a connected, undirected graph G=(V,E). A spanning tree of G is a subgraph of G, say T=(V′,E′), with the following properties:

  1. V′=V.
  2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree):

Consider an edge-weighted, connected, undirected graph G=(V,E). The minimum spanning tree T=(V,E′) of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E′.

Input

The first line contains a single integer t(1≤t≤100), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m(1≤n≤100), the number of nodes and edges. Each of the following m lines contains a triple (xi,yi,wi), indicating that xi and yi are connected by an edge with weight = wi.(1≤xi≤n,1≤yi≤n,xi≠yi,0≤wi≤10000).For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string Not Unique!

Sample input and output

Sample Input Sample Output
 
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
 
3
Not Unique!

Hint

The data used in this problem is unofficial data prepared by Nilil. So any mistake here does not imply mistake in the offcial judge data.

Source

POJ Monthly--2004.06.27 srbga@POJ
 
判断给定的图的最小生成树是否唯一，如果唯一输出最小生成树上所有树枝权值之和，否则输出Not Unique!
 
Kruskal求最小生成树。如果最小生成树不唯一，则必定存在权值相同的边。
 
 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m;
 5 struct EG
 6 {
 7     int x,y,w;
 8 }edge[5050];
 9 bool cmp(const EG & u,const EG & v)
10 {
11     return u.w < v.w;
12 }
13 class UFS{
14     public:
15     int fa[111],ra[111];
16 void ini()
17 {
18     int i;
19     for(i=1;i<=n;++i)ra[fa[i] = i] = 1;
20 }
21 int fin(int x)
22 {
23     if(fa[x] == x)return x;
24     return fa[x] = fin(fa[x]);
25 }
26 void uni(int x,int y)
27 {
28     int a = fin(x),b = fin(y);
29     if(a == b)return;
30     if(ra[a] < ra[b])
31     {
32         fa[a] = b;
33         ra[b] += ra[a];
34     }
35     else
36     {
37         fa[b] = a;
38         ra[a] += ra[b];
39     }
40 }
41 }s1,s2;
42 int main()
43 {
44     int t,i,ans,f;
45     scanf("%d",&t);
46 R:    while(t--)
47     {
48         scanf("%d%d",&n,&m);
49         s1.ini();
50         for(i=1;i<=m;++i)
51         {
52             scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
53             if(s1.fin(edge[i].x) != s1.fin(edge[i].y))s1.uni(edge[i].x,edge[i].y);
54         }
55         f = s1.fin(1);　　//判断图是否连通，否则直接输出0
56         for(i=2;i<=n;++i)
57         {
58             if(s1.fin(i) != f)
59             {
60                 puts("0");
61                 goto R;
62             }
63         }
64         sort(edge,edge + m + 1,cmp);
65         s2.ini();
66         ans = 0;
67         for(i=1;i<=m;++i)
68         {
69             if(s2.fin(edge[i].x) != s2.fin(edge[i].y))　　//如果第i条边可以被添加进来，
70             {
71                 if(i + 1 <= m && edge[i + 1].w == edge[i].w)　　//则看看下一条边（第（i+1）条边）是否和这条边权值相等；
72                 {
73                     if(s2.fin(edge[i + 1].x) != s2.fin(edge[i + 1].y))　　//且在第i条边被添加之前，第（i+1）条边是否就可以被添加。
74                     {
75                         s2.uni(edge[i].x,edge[i].y);　　//然后判断在第i条边被添加后，
76                         if(s2.fin(edge[i + 1].x) == s2.fin(edge[i + 1].y))　　//第（i+1）条边就不能被添加了。
77                         {　　　　　　　　　　　　　　　　　　//如果以上条件都满足，则说明第（i+1）条边可以在第i条边被添加之前就可以被添加进来，即树枝选择不唯一，
78                             puts("Not Unique!");　　　　//最小生成树也就不唯一。
79                             goto R;
80                         }
81                     }
82                 }
83                 s2.uni(edge[i].x,edge[i].y);
84                 ans += edge[i].w;
85             }
86         }
87         printf("%d\n",ans);
88     }
89     return 0;
90 }

 


联系
我们