POJ1679 The Unique MST（次小生成树(kruskal版)）

POJ1679 The Unique MST

题意：

判断在有n个点，m条边的无向图中最小生成树是否唯一

分析：

我想你一定会最小生成树了
不会的话先去学一波最小生成树再回来吧 传送门

例如下图：

我们很容易找到它的一颗最小生成树，如下图：

我们要找次小生成树，一定是每次把不在最小生成树中的边加入一条并把最小生成树中的边删除一条，使其任然是一棵树，然后取所有非最小生成树中最小的，即次小生成树
如上图，不在最小生成树中的边只有edge[1,5]和edge[1,6]

若把edge[1,5]加入，则1，3，5形成环，所以需要删除edge[1,3]、edge[3,5]和edge[5,1]中的一条边，显然edge[1,5]是新加入的，不能删，那么只能从edge[3,5]和edge[5,1]中删一条，要使新的树最小只能删最大的，即edge[1,3]，此时树的权值和为：1+2+2+1+7=13

以此类推：
若加入edge[1,6]则应该删去edge[1,3]，此时树的权值和为：1+2+2+1+4=10
显然10<13,所以次小生成树为第二棵

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
const int maxm = maxn * maxn;
int t, n, m;
bool vis[maxm];
int root[maxn];
int maxedge[maxn][maxn]; //maxedge[i][j]记录最小生成树中i，j两个节点之间的路径上长度最大的边长
vector<int> Group[maxn];
struct edge
{
    int u, v, w;
    bool operator<(const edge &e) const
    {
        return w < e.w;
    }
} Edge[2 * maxm];
int Find(int x)
{
    if (x == root[x])
        return x;
    return root[x] = Find(root[x]);
}
void kruskal()
{
    int sum = 0, cnt = 0;
    for (int i = 1; i <= m; ++i)
    {
        if (cnt == n - 1)
            break;
        int r1 = Find(Edge[i].u);
        int r2 = Find(Edge[i].v);
        if (r1 != r2)
        {
            ++cnt;
            vis[i] = 1;
            sum += Edge[i].w;
            // for (int j : Group[r1])
            // for (int k : Group[r2])
            // maxedge[j][k] = maxedge[k][j] = Edge[i].w;
            int len1 = Group[r1].size();
            int len2 = Group[r2].size();
            for (int j = 0; j < len1; ++j)
                for (int k = 0; k < len2; ++k)
                    maxedge[Group[r1][j]][Group[r2][k]] = maxedge[Group[r2][k]][Group[r1][j]] = Edge[i].w;
            // 再次吐槽POJ，都9102年了，连个C++11都不支持...
            root[r1] = r2;
            Group[r2].insert(Group[r2].end(), Group[r1].begin(), Group[r1].end());
        }
    }

    int _sum = inf;
    for (int i = 1; i <= m; ++i)
        if (!vis[i])
            _sum = min(_sum, sum - maxedge[Edge[i].u][Edge[i].v] + Edge[i].w);
    if (_sum == sum)
        printf("Not Unique!\n");
    else
        printf("%d\n", sum);
}
int main(int argc, char const *argv[])
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i)
            scanf("%d%d%d", &Edge[i].u, &Edge[i].v, &Edge[i].w);
        memset(vis, 0, sizeof vis);
        sort(Edge + 1, Edge + 1 + m);

        for (int i = 1; i <= n; ++i)
        {
            root[i] = i;
            Group[i].clear();
            Group[i].push_back(i);
        }

        kruskal();
    }
    return 0;
}