难道我少算了一步（28pts）

glass_goldfish @ 2024-07-04 15:23:22

#include<bits/stdc++.h>
using namespace std;
struct bian{long long fir,las,qz;}a[1000001];
long long n,x;
bool cmp(bian a,bian b){return a.qz<b.qz;}
long long cnt,ans;
long long fa[1000001];
long long fi(long long p){if(p==fa[p])return p;else return fi(fa[p]);}
int main()
{
    cin>>n>>x;
    for(long long i=1;i<=n;i++)
        fa[i]=i;
    for(long long i=1;i<=x;i++)
        cin>>a[i].fir>>a[i].las>>a[i].qz;
    sort(a+1,a+x+1,cmp);
    for(long long i=1;;i++){
        if(cnt==n-1)break;
        long long fa_fir=fi(a[i].fir);
        long long fa_las=fi(a[i].las);
        if(fa_fir==fa_las)continue;
        fa[a[i].las]=a[i].fir;
        ans+=a[i].qz;
        cnt++;
    }
    cout<<ans;
    return 0;
}//你回答我却不关注你我是狗

by sherry_lover @ 2024-07-04 15:29:34

没判输出orz的情况，应该还有其他错

by sherry_lover @ 2024-07-04 15:32:57

fa[a[i].las]=a[i].fir;应改为fa[fa_las] = a[i].fir;

by glass_goldfish @ 2024-07-04 15:34:28

@sherry_lover 还有什么错？求助

by aCssen @ 2024-07-04 15:37:21

不应该是 fa[fa_fir]=fa_las; 吗

by sherry_lover @ 2024-07-04 15:39:08

@aCssen 对

by glass_goldfish @ 2024-07-04 15:40:40

@sherry_lover @aCssen 最后一个点怎么办

by glass_goldfish @ 2024-07-04 15:43:03

@aCssen @sherry_lover
最后一个点数据：

in:
5 6
1 2 3
2 3 4
3 1 4
4 5 6
5 4 6
1 3 5
out:
orz

by aCssen @ 2024-07-04 15:50:08

到最后 cnt 还没到 n-1 就输出 orz。

by glass_goldfish @ 2024-07-04 15:54:39

@aCssen

#include<bits/stdc++.h>
using namespace std;
struct bian{long long fir,las,qz;}a[1000001];
long long n,x;
bool cmp(bian a,bian b){return a.qz<b.qz;}
long long cnt,ans;
long long fa[1000001];
long long fi(long long p){if(p==fa[p])return p;else return fi(fa[p]);}
int main()
{
    cin>>n>>x;
    for(long long i=1;i<=n;i++)
        fa[i]=i;
    for(long long i=1;i<=x;i++)
        cin>>a[i].fir>>a[i].las>>a[i].qz;
    sort(a+1,a+x+1,cmp);
    for(long long i=1;;i++){
        if(cnt==n-1)break;
        long long fa_fir=fi(a[i].fir);
        long long fa_las=fi(a[i].las);
        if(fa_fir==fa_las)continue;
        fa[fa_fir]=fa_las;
        ans+=a[i].qz;
        cnt++;
    }
    if(cnt+1!=n)cout<<"orz";//if(cnt+1<n)cout<<"orz";也是一样的结果
    else cout<<ans;
    return 0;
}//84pts,WA最后#13

by aCssen @ 2024-07-04 15:58:48

@liulijinyu 忘说了，枚举边的循环 i 是不能超过 x，就是说要这么写

for(long long i=1;i<=x;i++){
        long long fa_fir=fi(a[i].fir);
        long long fa_las=fi(a[i].las);
        if(fa_fir==fa_las)continue;
        fa[a[i].las]=a[i].fir;
        ans+=a[i].qz;
        cnt++;
        if(cnt==n-1)break;//这是为了考虑最后一条边
    }