讨论 / [题解]
dayuanjun 2019-01-26 09:51:47
点我顶贴 收藏 删除
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge

{

int u,v;

ll w;

}es[20005];

bool operator<(Edge e1,Edge e2)

{

return e1.w < e2.w;

}

int par[20005],tot[20005];

ll res;

void prep()

{

for(int i=1;i<=20005;i++)

{

par[i]=i;

tot[i]=1;

}

}

int fnd(int x)

{

if(x==par[x])

return x;

return par[x]=fnd(par[x]);

}

void unite(int u, int v,ll w)

{

int a=fnd(u);

int b=fnd(v);

res+=((tot[a]*tot[b]-1)*(w+1));

par[b]=a;

tot[a]+=tot[b];

}

int main()

{

int k;

scanf("%d",&k);

for(int i=1;i<=k;i++)

{

int n;

scanf("%d",&n);

for(int i=1;i<=n-1;i++)

{

scanf("%d%d%lld",&es[i].u,&es[i].v,&es[i].w);

}

sort(es,es+n);

prep();

for(int i=1;i<=n-1;i++)

{

res+=es[i].w;

unite(es[i].u,es[i].v,es[i].w);

}

printf("%lld\n",res);

res=0;

for(int i=1;i<=20005;i++)

{

es[i].u=0;es[i].v=0;es[i].w=0;

par[i]=0;tot[i]=0;

}

}

return 0;

}

此题根据最小生成树的概念:给了构成最小生成树的边,就说明它是那一步中(u,v)最小的,所以其它的至少大于,因为是完全图,所以两个集合间必定两两连边。综上,就按照构成最小生成树的步骤来,中途加入统计需要加的和

#1 mzyczly@2019-01-26 11:10:21
回复 删除
哈哈
#2 lucille璐@2019-01-27 10:46:20
回复 删除
.......
查看更多回复
提交回复