90求调
查看原帖
90求调
560291
the_Dream_Chaser楼主2024/1/8 17:21

RT,求大佬指点

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int i,j,k,num;
int K; 
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct Edge{
    int u,v,w;
}edge[MAXN];
int fa[MAXN],n,m,ans,eu,ev,cnt;
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
bool kruskal(){
    for(i=1;i<=m;i++)    {
        eu=find(edge[i].u);
		ev=find(edge[i].v);
        if(eu==ev)continue;
        ans+=edge[i].w;
        fa[eu]=ev;
        cnt++;
        if(cnt==n-k){cout<<ans<<endl;return 1;}
        
	}
	return 0;
}
int main(){
    n=read();m=read();k=read();
    //num=n;
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<=m;i++){
        edge[i].u=read();edge[i].v=read();edge[i].w=read();
    }
    sort(edge,edge+m+1,cmp);
    if(!kruskal())cout<<"No Answer"<<endl;
    return 0;
}

2024/1/8 17:21
加载中...