题目链接 (https://www.acwing.com/problem/content/861/)

算法基础课的859题，为什么最后的测试样例过不了，大佬们看看是哪里的问题

错误的代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n,m,f[N];
struct edge{
    int u,v,cost;
}e[2*N];
bool cmp(edge a,edge b){
    return a.cost<b.cost;
}
// int find(int a){
//     if(f[a] != a) f[a] = find(f[a]);
//     return f[a];
// }
int find(int x){
    int c = x;
    while(x!=f[x]){
        x = f[x];
    }
    while(c!=f[c]){
        int t = c;
        c = f[c];
        f[t] = x;
    }
    return x;
}

int krus(){
    int ans = 0,num = 0;
    for(int i=0; i<n; i++)  f[i] = i;
    sort(e,e+m,cmp);
    for(int i=0; i<m; i++){
        int fu = find(e[i].u),fv = find(e[i].v);
        if(fu!=fv){
            f[fu] = fv;
            ans += e[i].cost;
            num++;
            if(num==n-1)    break;
        }
    }
    if(num!=n-1)    return -1;
    else    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>e[i].u>>e[i].v>>e[i].cost;
    }
    int ans = krus();
    if(ans==-1) cout<<"impossible";
    else    cout<<ans;

    return 0;
}

提问于19天前

初渔

5041