谜之错误

P2820 局域网

看了一下,好像雀食有点问题。关键在于Kruskal的最小树有**n(顶点数)-1条边**,所以应该是 ```cpp if(edge==n) return; ``` 的 _edge==n_ 有问题,要改成**n-1** ------------ 我的AC代码:(友情提示,用不着long long) ```cpp #include <bits/stdc++.h> using namespace std; int f[110],n,e,num=0,ans=0,sum=0; int find(int x){ int r=x; while(r!=f[r]){ r=f[r]; } while(x!=f[x]){ x=f[x]; f[x]=r; } return r; } void uni(int x,int y){ int fx=find(x); f[fx]=find(y); } struct road{ int from,to,dis; }r[6010]; bool cmp(road a,road b){ return a.dis<b.dis; } int main(){ cin>>n>>e; for(int i=1;i<=105;i++){ f[i]=i; } for(int i=1;i<=e;i++){ cin>>r[i].from>>r[i].to>>r[i].dis; sum+=r[i].dis; } sort(r+1,r+e+1,cmp); for(int i=1;i<=e;i++){ if(find(r[i].from)!=find(r[i].to)){ num++; ans+=r[i].dis; uni(r[i].from,r[i].to); } if(num==n-1){ break; } } cout<<sum-ans; } ```
by NianFeng @ 2022-06-01 20:04:42


|