【POJ 1679】The Unique MST（Kruskal算法）

梦里梦外; 2022-02-15 08:53 149阅读 0赞

题目链接：[http://poj.org/problem?id=1679][http_poj.org_problem_id_1679]

### 题意： ###

给定一个连通的无向图，判断最小生成树是否唯一，唯一输出最小生成树的值，不唯一输出'Not Unique!'.

### 思路： ###

利用Kruskal算法，先生成一个最小生成树，记录生成树里的每一条边，然后枚举一个一个去掉这些边，看能否生成一个最小生成树，能则说明不唯一。

### My Code： ###

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    int f[105],cunt,n,m;
    struct Edge
    {
        int s,e,dis;
    }s[10005];
    int Find(int x)
    {
        if(x == f[x]) return x;
        else
        {
            int root = Find(f[x]);
            f[x] = root;
            return root;
        }
    }
    int cmp(Edge s1,Edge s2)
    {
        return s1.dis < s2.dis;
    }
    int path[100000];
    int Kruskal()
    {
        int cunt = 0;
        for(int i = 1; i <= n; i++)
            f[i] = i;
        sort(s,s+m,cmp);
        int ans = 0;
        for(int i = 0; i < m; i++)
        {
            int fa = Find(s[i].s);
            int fb = Find(s[i].e);
            if(fa != fb)
            {
                f[fa] = fb;
                ans += s[i].dis;
                path[cunt++] = i;///记录生成的最小生成树的边
            }
        }
        for(int j = 0; j < cunt; j++)///然后枚举去掉这些边，看其是否也能构成最小生成树且值相同
        {
            int sum = 0,k = 0;
            for(int i = 1; i <= n; i++)
                f[i] = i;
            for(int i = 0; i < m; i++)
            {
                if(i != path[j])
                {
                    int fa = Find(s[i].s);
                    int fb = Find(s[i].e);
                    if(fa != fb)
                    {
                        f[fa] = fb;
                        sum += s[i].dis;
                        k++;
                    }
                }
            }
            ///如果满足构成最小生成树，则说明最小生成树不唯一
            if(sum == ans && k == n-1) return -1;
        }
        return ans;
    }
    int main()
    {
        int t;
        cin >> t;
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int j = 0; j < m; j++)
                scanf("%d%d%d",&s[j].s,&s[j].e,&s[j].dis);
            cunt = m;
            int sum = Kruskal();
            if(sum == -1) printf("Not Unique!\n");
            else printf("%d\n",sum);
        }
    
        return 0;
    }

[http_poj.org_problem_id_1679]: http://poj.org/problem?id=1679