1 条题解

  • 0
    @ 2024-6-14 11:36:29
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const ll N=100005,M=300005;
    struct node1{
    	ll x,y,dist;
    	bool operator<(node1 k)const{
    		return dist<k.dist;
    	}
    }a[M];
    ll n,m,k,s,t,tot,fa[N];
    ll ans,ans1,z,zz;
    int getfa(ll x){
    	if (fa[x]==x) return x;
    	fa[x]=getfa(fa[x]);
    	return fa[x];
    }
    int main(){
    	//freopen("in.txt","r",stdin);
    	//freopen("out.txt","w",stdout);
    	cin>>n>>m;
    	for (int i=1;i<=m;++i)
    		cin>>a[i].x>>a[i].y>>a[i].dist;
    	sort(a+1,a+1+m);
    	for (int i=1;i<=n;++i) fa[i]=i;
    	z=0;zz=0;
    	for (int i=1;i<=m;++i){
    		s=getfa(a[i].x);
    		t=getfa(a[i].y);
    		if (s!=t){
    			++zz;
    			z+=a[i].dist;
    			fa[s]=t;
    		}
    	}
    	if (zz==n-1) cout<<z;
    	else cout<<"orz";
    }
    
    • 1

    信息

    ID
    820
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    6
    已通过
    2
    上传者