2021-10-01

题意

有一个无向图，问你边数不超过k且不出现环的最大总边权值为多少？

题解：

本题可以跑一个类似于Kruskal算法的最大生成树，用并查集维护不出现环。

代码：

#include 

using namespace std;

const int N = 100010;

struct Edge{
    int a, b, w;
    bool operator<(const Edge &A) const {
        return w > A.w;
    }
}edges[N];
int n, m, k, cnt;
int p[N];
typedef long long LL;
LL ans;
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void Kruskal()
{
    sort(edges + 1, edges + m + 1);
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    for(int i = 1; i <= m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int fa = find(a), fb = find(b);
        if(fa != fb)
        {
            cnt ++;
            p[fa] = fb;
            ans += w;
        }
        if(cnt == k){
            return;
        }
    }
}

int main()
{
    scanf("%d %d %d",&n, &m, &k);
    for(int i = 1; i <= m; i ++ )
    {
        int a, b, w;
        scanf("%d %d %d",&a, &b, &w);
        edges[i] = {a, b, w};
    }
    Kruskal();
    printf("%dn", ans);
    // system("pause");
    return 0;
}