84pts,WA on test13

__Alexander__ @ 2024-06-11 12:30:23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll father[maxn];
ll n,ans,point,m;
struct Node{
    int u,v,w;
    bool operator<(const Node other)const{
        return this->w<other.w;
    }
}node[maxn];
ll find(ll x){
    if(x==father[x]) return x;
    return father[x]=find(father[x]);
}
void f(){
    sort(node,node+m);
    for (int i=0;i<m;i++){
        int uu=find(node[i].u);
        int vv=find(node[i].v);
        if(uu==vv) continue;
        else{
            father[uu]=vv;
            ans+=node[i].w;
            point++;
            if(point==n-1) break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++) father[i]=i;
    for(int i=0;i<m;i++) cin>>node[i].u>>node[i].v>>node[i].w;
    ans=0,point=0;
    f();
    cout<<ans<<endl;
    if(point!=n-1) cout<<"orz"<<endl;
    return 0;
}

by lihongqian__int128 @ 2024-06-11 12:52:12

你不联通第一行还是输出了 ans。

by kevinZ99 @ 2024-06-11 12:54:52

@Xuzehou

你的输出有问题，不应该是先输出答案，在判断是否输出orz的啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll father[maxn];
ll n,ans,point,m;
struct Node{
    int u,v,w;
    bool operator<(const Node other)const{
        return this->w<other.w;
    }
}node[maxn];
ll find(ll x){
    if(x==father[x]) return x;
    return father[x]=find(father[x]);
}
void f(){
    sort(node,node+m);
    for (int i=0;i<m;i++){
        int uu=find(node[i].u);
        int vv=find(node[i].v);
        if(uu==vv) continue;
        else{
            father[uu]=vv;
            ans+=node[i].w;
            point++;
            if(point==n-1) break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++) father[i]=i;
    for(int i=0;i<m;i++) cin>>node[i].u>>node[i].v>>node[i].w;
    ans=0,point=0;
    f();
    if(point!=n-1) cout<<"orz"<<endl;
     else cout<<ans<<endl;
    return 0;
}

by __Alexander__ @ 2024-06-11 13:01:01

@lihongqian__int128 哦

by __Alexander__ @ 2024-06-11 13:01:17

@kevinZ99 感谢orz