如果你莫名其妙RE，且数组没开小

Small_Traveler @ 2024-10-29 18:00:05

by c_subtract_subtract @ 2024-10-29 18:15:15

????

by ZJ_lzz @ 2024-10-29 18:15:47

@Small_Traveler

感谢大佬

by c_subtract_subtract @ 2024-10-29 18:16:06

代码顺便发：

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e7;
int n,m,f[N],ans;
struct Node{int u,v,n;}a[N*10];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void unit(int x,int y){f[find(x)]=find(y);}
bool cmp(Node x,Node b){return x.n<b.n;}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].n;
    sort(a,a+m+1,cmp);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x=find(a[i].u),y=find(a[i].v);
        if(x!=y)
        {
            ans+=a[i].n;
            f[y]=x;
            cnt++;
            unit(x,y);
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"orz";
    else cout<<ans;
}

by shubowen @ 2024-11-24 10:29:34

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int s[5001];
int go(int i){
    if(i==s[i]){
        return i;
    }
    s[i]=go(s[i]);
    return s[i]; 
}
struct bian{
    int a,b;
    int quan;
}x[200001];
bool cmp(bian a,bian b){
    return a.quan<b.quan;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)s[i]=i;
    for(int i=1;i<=m;i++){
        cin>>x[i].a>>x[i].b>>x[i].quan;
    }
    sort(x+1,x+m+1,cmp);
    int w=n;
    for(int i=1;i<=m;i++){
        int t1=go(x[i].a);
        int t2=go(x[i].b);
        if(t1!=t2){
            ans+=x[i].quan;
            s[t1]=t2;
            w--;
            if(w==1){
                cout<<ans;
                return 0;
            }
        }
    }
    cout<<"orz";
    return 0;
}