The Unique MST(最小生成树的唯一路径）

51 阅读 0 评论 34 点赞

我是靠谱客的博主认真音响，最近开发中收集的这篇文章主要介绍The Unique MST(最小生成树的唯一路径），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最小生成树唯一的路径就是当前权值里，仅有一条路可以走，不存在最小权值一样的情况，如：1 2 2， 2 3 2， 1 3 2，第一次路径为1—2权值为2，但当下一次到3这个点时就存在分歧，因为1—3的权值是2，2—3的权值也是2，有两个选择。

例题： https://vjudge.net/contest/319242#problem/K

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

Sample Output

3
Not Unique!

解题思路：最短路径的prime算法，求出每一次到顶点的权值，然后比较各个点到最短边的权值是否有相同的，注意：会存在至少一条边满足相同，那就是本身这条边。

程序代码：

#include<stdio.h>
#include<string.h>
int e[2000][2000],dis[5000],book[5000];
int inf=99999999;
int main()
{
int i,j,k,n,m,t1,t2,t3,min,l,v,sun;
int count,sum;
int N,flag;
scanf("%d",&N);
while(N--)
{
flag=0;
count=0;
sum=sun=0;
l=1;
memset(dis,0,sizeof(dis));
memset(book,0,sizeof(book));
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(j==i)	e[i][j]=0;
else
e[i][j]=inf;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
if(e[t1][t2]>t3)//可能同样的边会出现两次，所以取较短的边
{
e[t1][t2]=t3;
e[t2][t1]=t3;
}
}
for(i=1;i<=n;i++)
dis[i]=e[1][i];
book[1]=1;
count++;
while(count<n)
{
min=inf;
for(i=1;i<=n;i++)
{
if(book[i]==0&&dis[i]<min)
{
min=dis[i];
j=i;
}
}
sun=0;//初始化有相同边的数目
for(v=1;v<=n;v++)//寻找n条边中已经标记的的边中是否有相同的边
if(book[v]==1&&min==e[v][j])
sun++;
if(sun>1)//sun>1说明最少有一条边与当前最小值一样
break;
book[j]=1;
sum+=dis[j];
count++;
for(k=1;k<=n;k++)
if(book[k]==0&&dis[k]>e[j][k])
dis[k]=e[j][k];
}
if(sun<=1)
printf("%dn",sum);
else
printf("Not Unique!n");
}
return 0;
}