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");
  }
}