次小生成树模板（以POJ 1679为例）

素颜马尾好姑娘i 2022-05-09 14:18 198阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：判断生成树的唯一性，唯一则输出权值，不唯一输出Not Unique! ##

## 分析：显然，可以转化为求次小生成树，次小生成树权值=最小生成树，则不唯一。我这里用的是kruscal算法，更加简单易用。入门参考[https://blog.csdn.net/li1615882553/article/details/80011884][https_blog.csdn.net_li1615882553_article_details_80011884]和[https://www.cnblogs.com/radical/p/3925487.html][https_www.cnblogs.com_radical_p_3925487.html]，代码有很详细的注释。   代码： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e2+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int t,n,m,p[N],vs[N*N],d[N][N];
    struct nd{
        int u,v,w;
        bool operator < (const nd &a) const {
            return w<a.w;
        }
    }eg[N*N];
    vector<int> g[N];
    
    int fd(int x) {
        while(x!=p[x])
            x=p[x];
        return x;
    }
    
    void kru() {
        for(int i=1;i<=n;i++) vs[i]=0,p[i]=i,g[i].clear(),g[i].pb(i);///初始化
        sort(eg+1,eg+m+1);
        int sum=0,kk=0;///sum是最小生成树的值 kk是最小生成树的节点数
        for(int i=1;i<=m;i++) {
            if(kk==n-1) break;
            int p1=fd(eg[i].u),p2=fd(eg[i].v);
            if(p1!=p2) {
                kk++;
                p[p1]=p2;
                sum+=eg[i].w;
                vs[i]=1;///这条边已经用过了
                for(int j=0;j<g[p1].size();j++)///更新两点之间距离的最大值
                    for(int k=0;k<g[p2].size();k++)
                        d[g[p1][j]][g[p2][k]]=d[g[p2][k]][g[p1][j]]=eg[i].w;///因为后面的边会越来越大，所以这里可以直接等于当前边的长度
                for(int j=0;j<g[p1].size();j++) g[p2].pb(g[p1][j]);///现在已经属于一棵树了，那么我们就将点添加到相应的集合中
            }
        }
        int csum=inf;///次小生成树的权值
        for(int i=1;i<=m;i++)
            if(!vs[i]) csum=min(csum,sum+eg[i].w-d[eg[i].u][eg[i].v]);
        if(sum!=csum) printf("%d\n",sum);
        else printf("Not Unique!\n");
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
        while(~scanf("%d",&t)) {
            while(t--) {
                scanf("%d%d",&n,&m);
                for(int i=1;i<=m;i++)
                    scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
                kru();
            }
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1679
[https_blog.csdn.net_li1615882553_article_details_80011884]: https://blog.csdn.net/li1615882553/article/details/80011884
[https_www.cnblogs.com_radical_p_3925487.html]: https://www.cnblogs.com/radical/p/3925487.html