The Unique MST - POJ 1679 次小生成树

The Unique MST

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 19125	Accepted: 6684

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!      

题目大意：

        给你t组数据，每组数据有m个点,n个可以连接的边，问你把所有点连接起来的最小距离是否为一种连接方法，如果是输出最短距离，如果有多重连接方法输出 Not Unique!

个人思路：

        这道题和Agri-Net - POJ 1258 题差不多，详情见    http://blog.csdn.net/u014733623/article/details/23866901

        用Prime()在找最短距离的同时设一个数组p[]表示当前的点连到j点的最短距离有多少个，比如说你当前有 1,2两点，他们连接到4点的距离分别为2、3，那么p[4]=1，因为连到4点最短距离为2，且有只有1个，这时你又连接了第3个点，3到4的距离也为2，那么p[4]=2，最短距离2有两个了。然后你再连接第4个点的时候，4可以连接1，也可以连接3，距离最小且都是2，那么这时最短距离的连接方法就不只一种了，所以输出Not Unique!

下面是AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[110][110];    //a[][]为输入的矩阵
int n,m,ans;
int d[110];         //d[]为当前已连接的点的集合到还未连接的点的最小距离
int visit[110];     //visit[]标记已经连接的点
int p[110];         //p[]表示当前已有的点连接到第j个点的最短距离有多少个，用于判断是否为Unique
bool flag;          //记录是否为Unique
const int INF=100000000;
void Prime()
{ int i,j;
  for(i=1;i<=n;i++)
   d[i]=-1;          //可能有的点之间不能连接
  d[1]=0;           //对于最开始的时候让d[1]=0，其他为无穷大，使第一次循环的时候连接第一个点
  memset(visit,0,sizeof(visit));
  memset(p,0,sizeof(p));
  for(i=1;i<=n;i++)
  { int pos=INF,mi=INF;  //pos为d[]表示的距离中距离最短的点的指针，mi表示最短的距离
    for(j=1;j<=n;j++)    //找到该点
     if(!visit[j] && d[j]>=0 && d[j]<=mi) //要连接的那点要求没有搜索过并且可以连接
     { pos=j;
       mi=d[j];
     }
    visit[pos]=1;     //visit[]记录的已连接的点就不用考虑了
    if(p[pos]>=2)     //如果当前已有的点连接到第j个点的最短距离有两个或两个以上，说明该点可以连接不同的点
     {flag=false;break;}     //所以为Not Unique!
    ans+=mi;          //总的长度加上这个最短距离
    for(j=1;j<=n;j++)   //现在你已连接的点（第pos个点）又多了一个，那么你再连接其他点的最短距离可能会更短
     if(!visit[j] && a[pos][j]>=0)
     { if(a[pos][j]<d[j] || d[j]<0)
        { d[j]=a[pos][j];
          p[j]=1;
        }
       else if(a[pos][j]==d[j])
         p[j]++;
     }
  }
}
int main()
{ int t,i,j,k,xi,yi,wi;
  scanf("%d",&t);
  while(t--)
  { memset(a,-1,sizeof(a));
    scanf("%d%d",&n,&m);
    ans=0;
    flag=true;
    for(i=1;i<=m;i++)
    { scanf("%d%d%d",&xi,&yi,&wi);
      a[xi][yi]=wi;
      a[yi][xi]=wi;
    }
    Prime();
    if(flag)
     printf("%d\n",ans);
    else
     printf("Not Unique!\n");
  }
}