P2121拆地毯题解

__S08577__ · 2024-09-27 19:28:57 · 题解

思路

这道题挺简单的。

首先题目说明，连成的图中不能有环，说明只能是一棵树。而要求整个树上的边权最大，不难想到最大生成树我们只需要求出只有 k 条边时的最大生成树即可。

代码

struct id{
    int x,y,w;
}a[N];
int fa[N];

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

bool cmp(id a ,id b){
    return a.w>b.w;//与最小生成树的唯一区别
}
int n,m;
int k;
int ans=0,edge=0,sum=0;
void Kruscal(){
    for(int i=1;i<=m;i++){
        int u=find(a[i].x),v=find(a[i].y);
        if(u==v) continue;
        ans+=a[i].w;
        fa[u]=v;
        edge++;
        if(edge==n-1||edge==k) break;
    }
}