PAT (Top Level) Practise 1016 Uniqueness of MST (35)

1016. Uniqueness of MST (35)

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

CHEN, Yue

Given any weighted undirected graph, there exists at least one minimum spanning tree (MST) if the graph is connected. Sometimes the MST may not be unique though. Here you are supposed to calculate the minimum total weight of the MST, and also tell if it is unique or not.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<= 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by 3 integers:

V1 V2 Weight

where V1 and V2 are the two ends of the edge (the vertices are numbered from 1 to N), and Weight is the positive weight on that edge. It is guaranteed that the total weight of the graph will not exceed 230.

Output Specification:

For each test case, first print in a line the total weight of the minimum spanning tree if there exists one, or else print "No MST" instead. Then if the MST exists, print in the next line "Yes" if the tree is unique, or "No" otherwise. If there is no MST, print the number of connected components instead.

Sample Input 1:

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5      

Sample Output 1:

11
Yes      

Sample Input 2:

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3      

Sample Output 2:

4

No

Sample Input 3:

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3      

Sample Output 3:

No MST

2

給出一張圖，判斷是否有最小生成樹，如果有，是否唯一。

直接上Kruskal算法，唯一的難點是判斷是否唯一，為了簡單的寫，

#include<map> 
#include<set>
#include<ctime>  
#include<cmath>      
#include<queue>   
#include<string>  
#include<vector>  
#include<cstdio>      
#include<cstring>    
#include<iostream>  
#include<algorithm>      
#include<functional>  
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))      
#define rep(i,j,k) for(int i=j;i<=k;i++)      
#define per(i,j,k) for(int i=j;i>=k;i--)      
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])      
#define inone(x) scanf("%d",&x)      
#define intwo(x,y) scanf("%d%d",&x,&y)      
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)    
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)   
#define lson x<<1,l,mid  
#define rson x<<1|1,mid+1,r  
#define mp(i,j) make_pair(i,j)  
#define ft first  
#define sd second  
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
const double eps = 1e-10;
int n, m, a[N], x[N], y[N], z[N], fa[N], ans, cnt, tot;

bool cmp(int x, int y) { return z[x] < z[y]; }

int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }

int main()
{
  intwo(n, m);
  rep(i, 1, m) inthr(x[i], y[i], z[i]);
  rep(i, 1, n) fa[i] = i;
  rep(i, 1, m) a[i] = i;
  cnt = n; ans = tot = 0;
  sort(a + 1, a + m + 1, cmp);
  for (int i = 1, j; i <= m; i = j)
  {
    for (j = i; j <= m&&z[a[i]] == z[a[j]]; j++)
    {
      int fx = get(x[a[j]]), fy = get(y[a[j]]);
      if (fx == fy) continue; else tot++;
    }
    for (j = i; j <= m&&z[a[i]] == z[a[j]]; j++)
    {
      int fx = get(x[a[j]]), fy = get(y[a[j]]);
      if (fx == fy) continue;
      fa[fx] = fy; ans += z[a[j]]; cnt--;
    }
  }
  if (cnt > 1) printf("No MST\n%d\n", cnt);
  else printf("%d\n%s\n", ans, tot < n ? "Yes" : "No");
  return 0;
}