AcWing 346. 走廊泼水节
原题链接
中等
作者:
ZTEG
,
2019-11-26 08:46:54
,
所有人可见
,
阅读 2580
改一下最小生成树模板就能过辣
在并查集求最小生成树模板上加一个tot数组存这个并查集内节点的个数,再跑最小生成树模板统计答案就AC辣
#include<bits/stdc++.h>
using namespace std;
struct oppo {
int from,to,s;
} rood[9000000];
int fa[7000];
int tot[7000];
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool rule(oppo a,oppo b) {
return a.s<b.s;
}
int n,T;
int ans;
int main() {
cin>>T;
while(T--) {
cin>>n;
ans=0;
for(int i=1; i<n; i++)
scanf("%d%d%d",&rood[i].from,&rood[i].to,&rood[i].s);
for(int i=1; i<=n; i++) {
fa[i]=i;
tot[i]=1;
}
sort(rood+1,rood+n,rule);
for(int i=1; i<n; i++) {
int a=find(rood[i].from);
int b=find(rood[i].to);
fa[b]=a;
ans+=(rood[i].s+1)*(tot[a]*tot[b]-1);
tot[a]+=tot[b];
}
cout<<ans<<endl;
}
return 0;
}
嘛了麻了
这个哪错了,我自己写了一下,就差照抄了
n个点的完全图是唯一的 咋可能让完全图的唯一最小生成树仍然是这棵树呢。
?你指的什么唯一,你的不同又是怎么定义的?
我现在懂了 谢谢
哥们, 我也以为n个点的完全图是唯一的, 教教我。
增加的边的边权是不一定的,所以我们可以通过设置添加的边的边权,来使得最后的完全图的最小生成树是原树,这也是这道题目让我们求的(求添加的总边权最小是多少)。
也就是说 n个点的完全图是唯一的 但是增加的边的边权是不一定的
老哥我昨晚也才懂, 谢谢了
哈哈 加油
老哥加油