玄关求调
查看原帖
玄关求调
1055811
RADMisanthrope楼主2025/1/22 10:04

参考了第一篇大佬的题解,但是0pts 求各位佬看看, ORZ ORZ

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 1;
struct node{
    int s,e,w;
}a[N];
int fa[N];
bool cmp(node a,node b)
{
    return a.w < b.w;
}
int find_father(int a)
{
    if(fa[a] = a) return a;
    else return fa[a] = find_father(fa[a]);
}

int n,m,k;

int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++)
    {
        fa[i] = i;
    }
    for(int i = 1;i <= m;i ++)
        cin >> a[i].s>> a[i].e>> a[i].w;
    sort(a + 1,a +m +1,cmp);
    int cnt = 0,sum = 0;
    for(int i = 1;i <= m;i ++)
    {
        if(find_father(a[i].s) != find_father(a[i].e))
        {
            fa[find_father(a[i].s)] = find_father(a[i].e);
            sum += a[i].w;
            cnt ++;
        }
        if(cnt >= n - k)
            break ;
    }
    if(cnt >= n - k) cout << sum;
    else cout << "No Answer";
//    cout << "Hello world!" << endl;
    return 0;
}
2025/1/22 10:04
加载中...