poj 1679 The Unique MST 【次小生成树】【模板】

清疚 2022-08-13 14:59 141阅读 0赞

题目：[poj 1679 The Unique MST][]

题意：给你一颗树，让你求最小生成树和次小生成树值是否相等。

分析：这个题目关键在于求解次小生成树。

方法是，依次枚举不在最小生成树上的边，然后添加到最小生成树上，然后把原树上添加了之后形成环的最长的边删去，知道一个最小的。就是次小生成树。

这些需要的都可以在求解最小生成树的时候处理出来。

AC代码：

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <vector>
    #define Del(a,b) memset(a,b,sizeof(a))
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 550;
    int mp[N][N];
    bool vis[N],used[N][N];
    int pre[N],ma[N][N],cost[N];
    int n,m;
    int Prim(int x)
    {
        int ans = 0;
        Del(ma,0);
        Del(used,false);
        for(int i=1;i<=n;i++)
        {
            cost[i] = mp[x][i];
            pre[i] = 1;
            vis[i] = false;
        }
        vis[x] = true;
        pre[x] = -1;
        for(int i=1;i<n;i++)
        {
            int minc = inf;
            int  p = -1;
            for(int j=1;j<=n;j++)
            {
                if(vis[j]==false && minc>cost[j])
                {
                    minc = cost[j];
                    p = j;
                }
            }
            if(p==-1)
                return -1;
            ans+=minc;
            vis[p] = true;
            int tmp = pre[p];
            used[p][tmp] = used[tmp][p] = true; //MST上的边
            for(int j=1;j<=n;j++)
            {
                if(vis[j])
                    ma[j][p] = ma[p][j] = max(ma[j][tmp],cost[p]);
                if(vis[j]==false && cost[j]>mp[p][j])
                {
                    cost[j] = mp[p][j];
                    pre[j] = p;
                }
            }
        }
        return ans;
    }
    int Next_Prim(int x)
    {
        int ans = inf;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(mp[i][j]!=inf && !used[i][j]) //枚举不在MST上的边替换
                    ans = min(ans,x+mp[i][j]-ma[i][j]);
            }
        }
        return ans;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(mp,inf,sizeof(mp));
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                mp[x][y] = mp[y][x] = z;
            }
            int ans = Prim(1);
            int next = Next_Prim(ans);
            //printf("%d %d\n",ans,next);
            if(ans!=next)
                puts("No");
            else
                puts("Yes");
        }
        return 0;
    }

[poj 1679 The Unique MST]: http://poj.org/problem?id=1679