题目大意

求最小生成树和非严格次小生成树。

解题思路

感觉难度应该只有绿。

最小生成树：参考 kruskal（我的远古博客，不要介意）。

非严格次小生成树：显然次小生成树一定是最小生成树去掉一条边再添加一条新边形成的。于是我们可以枚举这些边将它删掉（将它屏蔽掉）再求一遍最小生成树，得到的值取最小就是次小生成树。

时间复杂度 \(\mathcal{O}(nm\log m)\)。

CODE

#include <bits/stdc++.h>

using namespace std;

int T, n, m;

int fa[2007];

struct Edge
{
    int u, v, dis;
} D[100007];

vector<int> t;

bool cmp(Edge a, Edge b)
{
    return a.dis < b.dis;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

signed main()
{
    scanf("%d", &T);
    while (T--)
    {
        t.clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            fa[i] = i;
        for (int i = 1; i <= m; ++i)
            scanf("%d%d%d", &D[i].u, &D[i].v, &D[i].dis);
        sort(D + 1, D + m + 1, cmp);
        int cnt = 0, ans1 = 0;
        for (int i = 1; i <= m; ++i)
        {
            int u = D[i].u, v = D[i].v, d = D[i].dis;
            int x = find(u), y = find(v);
            if (x != y)
            {
                fa[x] = y;
                ans1 += d;
                t.push_back(i);
                if (++cnt == n - 1)
                    break;
            }
        }
        int ans2 = INT_MAX;
        for (int i = 0; i < t.size(); ++i)
        {
            cnt = 0;
            for (int j = 1; j <= n; ++j)
                fa[j] = j;
            int res = 0;
            for (int j = 1; j <= m; ++j)
            {
                if (j == t[i])
                    continue;
                int u = D[j].u, v = D[j].v, d = D[j].dis;
                int x = find(u), y = find(v);
                if (x != y)
                {
                    fa[x] = y;
                    res += d;
                    if (++cnt == n - 1)
                    {
                    	ans2 = min(ans2, res);
                        break;
                    }
                }
            }
        }
        printf("%d %d\n", ans1, ans2);
    }
    return 0;
}