合并是fa[father(ac[i].x)]=fa[father(ac[i].y)]吧
by lrj124 @ 2017-08-25 18:55:53
@[凭栏](/space/show?uid=48392)
by lrj124 @ 2017-08-25 18:56:29
@[lrj124](/space/show?uid=17521) 可是在判断的时候不是已经把他们的father全更新成了祖先了吗?
by Miri @ 2017-08-25 18:58:43
哦,是fa[father(ac[i].x)]=father(ac[i].y)
by lrj124 @ 2017-08-25 19:01:29
帮你改了改,ac了,\*表示改过的
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
struct Accepted {
int x,y,s;
} ac[20000];
int fa[20000],dis[2000][2000];
int cmp(const Accepted &a,const Accepted &b) {
return a.s<b.s;
}
int father(int a) {
if(fa[a]==a) return a;
else {
fa[a]=father(fa[a]);
return fa[a];
}
}
int main() {
int n,k,l=0,a,b,c,tot=0,ans=0;
cin>>n>>k;
for(int i=1; i<=n; i++)
fa[i]=i;
for(int i=1; i<=k; i++) {
cin>>a>>b>>c;
dis[a][b]=dis[b][a]=c;
}
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(dis[i][j]) {
ac[++l].s=dis[i][j];
tot+=dis[i][j];
ac[l].x=i;
ac[l].y=j;
}
* sort(ac+1,ac+l+1,cmp);
* int cnt=0;
* for(int i=1; i<=l; i++)
if(father(ac[i].x)!=father(ac[i].y)) {
ans+=ac[i].s;
* ++cnt;
* fa[father(ac[i].x)]=father(ac[i].y);
* if(cnt==n-1) break;
}
cout<<tot-ans<<endl;
return 0;
}
```
by lrj124 @ 2017-08-25 19:09:48
@[凭栏](/space/show?uid=48392)
by lrj124 @ 2017-08-25 19:10:31
@[lrj124](/space/show?uid=17521) 天哪!你好用心啊!你真是个善良的好人那!(感动 /(ㄒoㄒ)/~~
by Eternity_ @ 2017-08-25 19:15:35
@[lrj124](/space/show?uid=17521) 不好意思,刚才是我的小号,我不小心用小号回你了,嘿嘿
by Eternity_ @ 2017-08-25 19:16:48
@[lrj124](/space/show?uid=17521) 用大号再来说一声谢谢~~\(≧▽≦)/~谢谢大佬那~
by Miri @ 2017-08-25 19:17:57
@[凭栏](/space/show?uid=48392) 我是蒟蒻
by lrj124 @ 2017-08-25 19:45:46