题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 105, K = 205;

struct Edge{
    int a, b, c;
    bool operator <(const Edge &W)const
    {
        return c < W.c;
    }
}edges[K];
int n, k;
int p[N];

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    sort(edges, edges + k);

    for (int i = 1; i <= n; i ++) p[i] = i;

    int res = 0;
    for (int i = 0; i < k; i ++)
    {
        int a = find(edges[i].a), b = find(edges[i].b), w = edges[i].c;
        if (a != b) p[a] = b;//这些边都是要去掉的边；
        else res += w;
    }
    cout << res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla