【次小生成树】PAT (Top Level) 1016 Uniqueness of MST (35)

ゝ一纸荒年。 2022-06-04 08:35 149阅读 0赞

Think:  
1知识点：次小生成树  
2题意：  
（1）：若最小生成树存在且唯一，第一行输出最小生成树权值和，第二行输出Yes  
（2）：若最小生成树存在且不唯一，第一行输出最小生成树权值和，第二行输出No  
（3）：若最小生成树不存在即图不连通，第一行输出”No MST”，第二行输出连通块数量  
3反思：  
（1）：次小生成树代码实现部分i与j不要混淆  
（2）：次小生成树代码实现部分试探标记不要忘记当前边试探完成之后及时取消

[PAT题集-题目链接][PAT_-]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Edge{
      int u, v, w;
      int flag;
      bool operator < (const Edge &b) const{
        return w < b.w;
      }
    }edge[404014];
    
    int f[504];
    int tp, link[404014];
    
    void init_f(int n);
    int get_f(int x);
    bool Merge(int x, int y);
    
    int main(){
      int n, m, num, sum;
      while(~scanf("%d %d", &n, &m)){
        for(int i = 0; i < m; i++){
          scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
          edge[i].flag = 0;
        }
        sort(edge, edge+m);/*按边权升序排序*/
        init_f(n);/*Kruskal算法并查集标记数组初始化初始化*/
        tp = 0, num = 0, sum = 0;/*路径记录变量以及Kruskal算法记录变量初始化*/
        for(int i = 0; i < m; i++){
          if(Merge(edge[i].u, edge[i].v)){
            num++;
            sum += edge[i].w;
            link[tp++] = i;
            if(num == n-1) break;
          }
        }
        if(num != n-1){
          int cnt = 0;
          for(int i = 1; i <= n; i++){
            if(f[i] == i) cnt++;/*查询图内有几个连通块*/
          }
          printf("No MST\n");
          printf("%d\n", cnt);/*输出图内连通块的数量*/
        }
        else {
          printf("%d\n", sum);
          int i, id, cnt, tmp;
          for(i = 0; i < tp; i++){
            id = link[i];
            edge[id].flag = 1;/*标记试探边*/
    
            /*Kruskal算法*/
            init_f(n);
            cnt = 0, tmp = 0;
            for(int j = 0; j < m; j++){
              if(edge[j].flag == 0){
       /*判断当前边是否为试探边*/
                if(Merge(edge[j].u, edge[j].v)){
       /*尝试下标为j的边是否可以加入当前的生成树*/
                  cnt++;
                  tmp += edge[j].w;/*反思：j不要与i混淆写错*/
                  if(cnt == n-1) break;
                }
              }
            }
    
            edge[id].flag = 0;/*试探边试探完成之后取消试探标记*/
    
            if(cnt == n-1 && tmp == sum) break;/*判断最小生成树是否唯一*/
          }
          if(i < tp) printf("No\n");/*提前终止代表最小生成树不唯一*/
          else printf("Yes\n");
        }
      }
      return 0;
    }
    void init_f(int n){
      for(int i = 0; i <= n; i++){
        f[i] = i;
      }
      return;
    }
    int get_f(int x){
      if(x == f[x]) return x;
      return f[x] = get_f(f[x]);
    }
    bool Merge(int x, int y){
      int t1 = get_f(x);
      int t2 = get_f(y);
      if(t1 != t2){
        f[t2] = t1;
        return true;
      }
      return false;
    }

[PAT_-]: https://www.patest.cn/contests/pat-t-practise/1016