题目链接 (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