错哪里了啊,求助大佬,wa第4个和第8个
  • 板块P1195 口袋的天空
  • 楼主zldy
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/10 10:29
  • 上次更新2023/10/27 03:33:10
查看原帖
错哪里了啊,求助大佬,wa第4个和第8个
601674
zldy楼主2022/11/10 10:29
#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int from,to,value;
};
Edge e[10002];
const bool operator<(const Edge&l,const Edge&r){
    return l.value<r.value;
}
int fa[1002];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[x]=y;
    return ;
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y,l;
        cin>>x>>y>>l;
        e[i]=Edge{x,y,l};
    }
    sort(e+1,e+m);
    int cnt=0,ans=0;
    for(int i=1;i<=m;i++){
        int x=find(e[i].from),y=find(e[i].to);
        if(x==y) continue;
        merge(x,y);
        cnt++;
        ans+=e[i].value;
        if(cnt==n-k) break;
    }
    if(cnt<n-k){
        cout<<"No Answer"<<"\n";
        return 0;
    }
    cout<<ans<<"\n";
    return 0;
}
2022/11/10 10:29
加载中...