次小生成树模板

整体思路就是将没有用过的边插入最小生成树中，会形成一个环，我们去掉这个环中最大的那个边，会得到一个新的

生成树，次小生成树就是新的生成树中最小的那个。我们用一个数组maxx来记录最小生成树中两点之间最大的权值。

用connect数组表示边是否加入最小生成树中，代码如下：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 105, M = 10005;
int INF = 99999999;

int map[N][N], connect[N][N], maxx[N][N], n, m;
int prim()
{
    int mark[N], sum = 0, father[N], dis[N];
    fill(mark, mark + N, 0);
    for (int i = 1; i <= n; i++)
    {
        father[i] = 1;
        dis[i] = map[1][i];
    }
    dis[1] = 0, mark[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        int min1 = INF, u = -1;
        for (int j = 1; j <= n; j++)if(mark[j] == 0 && min1 > dis[j])
        {
            u = j, min1 = dis[j];
        }
        connect[u][father[u]] = connect[father[u]][u] = 2;
        maxx[u][father[u]] = maxx[father[u]][u] = min1;
        sum += min1;
        mark[u] = 1;

        for (int j = 1; j <= n; j++)
        {
            if(mark[j] == 1 && j != u)
            {
                maxx[j][u] = maxx[u][j] = max(maxx[j][father[u]], maxx[father[u]][u]);   //更新在最小生成树中两点之间最大的权值
            }
            if(mark[j] == 0 && dis[j] > map[u][j])
            {
                dis[j] = map[u][j];
                father[j] = u;
            }
        }
    }
    return sum;
}
/*
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

*/
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        fill(connect[0],connect[0] +  N * N, 0);
        fill(maxx[0], maxx[0] + N * N, 0);
        fill(map[0], map[0] + N * N, INF);
        for (int i = 1; i <= m; i++)
        {
            int x, y, w;
            scanf("%d %d %d", &x, &y, &w);
            map[x][y] = map[y][x] = w;
            connect[x][y] = connect[y][x] = 1;
        }
        int res1 = prim();
        int flag = 0;
        int res2 = INF + INF;
        for (int i = 1; i <= n && flag == 0; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (connect[i][j] == 1 )
                {
                    res2 = min(res2, res1 + map[i][j] - maxx[i][j]);
                }
            }
        }
 
        if(res2 != res1)
        {
            printf("%d %d\n", res1,res2);
        }
        else
        {
            printf("Not Unique!\n");
        }
    }

    return 0;
}