学步园

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'.

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.

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

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!
题目意思是：在给定的数据中，找到一棵最小生成树，如果这棵最小生成树是唯一的那么就输出最小生成树上权的和，不是唯一的就输出Not Unique!
解法：先建立一棵最小生成树，然后找一条边不在最小生成树上，把这条边作为起始边开始建最小生成树，如果找到一棵最小生成树与第一次建的最小生成树权值相等，那么就不用再找了，直接输出Not Unique!
#include<stdio.h>
#include<string.h>
typedef struct sn
{
    int v;//用于记录与当前点相连的点
    int dist;//权值
}Node;
Node node[105];
int n,s[105],vist[105][105],map[105][105],INF=1000000;
void set_first(int n)//初始化
{
    for(int i=1;i<=n;i++)
        {
            s[i]=0; node[i].dist=INF;
            for(int j=i+1;j<=n;j++)
                 map[i][j]=map[j][i]=INF;
        }
        memset(vist,0,sizeof(vist));
}
int Prim(int m,int sum,int flog)
{
    int tm=m,min,i;
    s[m]=1;
    if(flog==0)i=2;//如果flog=0就是s集合己有1个点，否则有2个点
    else  i=3;
    for( ;i<=n;i++)
    {
        min=INF;
        for(int j=1;j<=n;j++)
        if(s[j]==0)
        {
            if(node[j].dist>map[tm][j])//更新权值，并且更新与j相连的点tm
            {
                node[j].dist=map[tm][j];
                if(flog==0)
                node[j].v=tm;
            }

            if(min>node[j].dist)//找到最小的权值并记录点位置
            {
                min=node[j].dist; m=j;
            }
        }
            sum+=min; tm=m; s[m]=1;
            if(flog==0)
            vist[node[m].v][m]=vist[m][node[m].v]=1;//为1时边在最小生成树上，否则不在树上
    }
    return sum;
}
int main()
{
    int t,a,b,w,m,sum1,sum2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
         set_first(n);//初始化
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&w);
            if(map[a][b]>w)//判断重边
            map[a][b]=map[b][a]=w;
        }
        sum1=Prim(1,0,0);
        int flog=0;
        for(int i=1;i<n;i++)//找一条不在最小生成树上的边，然后从这条边开始建树
        {
            for(int j=i+1;j<=n;j++)//从i+1开始为了不重复，因为如：1到2和2到1是一样的
            if(vist[i][j]==0&&map[i][j]!=INF)
            {
                 for(int e=1;e<=n;e++)//初始化
                 {
                     s[e]=0; node[e].dist=INF;
                 }
                 s[i]=1;//加入第一个点
                 for(int e=1;e<=n;e++)//更新与第一个点相关的点
                 {
                     node[e].dist=map[i][e];
                 }
                sum2=Prim(j,node[j].dist,1);//从点j开始找
                if(sum2==sum1){flog=1;break;}//找到有多种可能，跳出
            }
            if(flog)break;
        }

        if(flog==0)
        printf("%d\n",sum1);
        else
        printf("Not Unique!\n");
    }
}