POJ - 1679 The Unique MST （最小生成树）

Dear 丶 2022-05-18 06:59 167阅读 0赞

#                                      The Unique MST #

### Description ###

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 <= 20), 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. 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 ###

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

### Sample Output ###

3
    Not Unique!

**题意描述：**  
给出n个点及它们之间的路径判断它们的最小生成树是否唯一，若唯一输出结果，不唯一输出“Not Unique!”

**解题思路：**

先利用Kruskal算法求出最小生成树结果sum，将形成最小生成树的路径进行标记，再利用枚举法，每次去掉一个最小生成树的边，用其他边代替，若能找到最小生成树的结果还为sum即说明最小生成树不唯一；

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int f[1010],n,m;
    struct A
    {
    	int a;
    	int b;
    	int c;
    	int h;
    }q[100010];
    int cmp(struct A x,struct A y)
    {
    	return x.c<y.c;
    }
    int get(int i)
    {
    	if(f[i]==i)
    		return i;
    	else
    	{
    		f[i]=get(f[i]);
    		return f[i];
    	}
    }
    int merge(int u,int v)
    {
    	int t1;
    	int t2;
    	t1=get(u);
    	t2=get(v);
    	if(t1!=t2)
    	{
    		f[t2]=t1;
    		return 1;
    	}
    	return 0;
    }
    int kush(int x)
    {
    	int i,sum,cut;
    	for(i=1;i<=n;i++)
    		f[i]=i;
    	sum=0;
    	cut=0;
    	for(i=1;i<=m;i++) 
    	{
    		if(i==x)//跳过这条已用过的边 
    			continue;
    		if(merge(q[i].a,q[i].b))
    		{
    			sum=sum+q[i].c;
    			cut++;
    		}
    		if(cut==n-1)
    			return sum;
    	}
    	return -1;
    }
    int main()
    {
    	int t,i,j,sum,cut,ans,flag;
    	while(scanf("%d",&t)!=EOF)
    	{
    		while(t--)
    		{
    			scanf("%d%d",&n,&m);
    			for(i=1;i<=m;i++)
    			{
    				scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
    				q[i].h=0;
    			}
    			sort(q+1,q+m+1,cmp);
    			for(i=1;i<=n;i++)
    				f[i]=i;
    			sum=0;
    			cut=0;
    			//Kruskal
    			for(i=1;i<=m;i++)
    			{
    				if(merge(q[i].a,q[i].b))
    				{
    					sum=sum+q[i].c;
    					q[i].h=1;
    					cut++;
    				}
    				if(cut==n-1)
    					break;
    			}
    			flag=0;
    			for(i=1;i<=m;i++)
    			{
    				if(q[i].h==1)//枚举每次减去一条边 
    					ans=kush(i);
    				if(sum==ans)//若相等说明最小生成树已不是唯一，结束循环 
    				{
    					flag=1;
    					break;
    				}
    			}
    			if(flag==1)
    				printf("Not Unique!\n");
    			else
    				printf("%d\n",sum);
    		}
    	}
    	return 0;
    }