[TYVJ1391]走廊泼水节

Description

话说，中中带领的OIER们打算举行一次冬季泼水节，当然这是要秘密进行的，绝对不可以让中中知道。不过中中可是老江湖了，当然很快就发现了我们的小阴谋，于是他准备好水枪迫不及待的想要加入我们了。我们一共有N个OIER打算参加这个泼水节，同时很凑巧的是正好有N个水龙头(至于为什么，我不解释)。N个水龙头之间正好有N-1条小道，并且每个水龙头都可以经过小道到达其他水龙头(这是一棵树，你应该懂的..)。但是OIER门为了迎接中中的挑战，决定修建一些个道路(至于怎么修，秘密_{),使得每个水龙头到每个水龙头之间都有一条直接的道路连接(也就是构成一个完全图呗})。但是OIER门很懒得，并且记性也不好，他们只会去走那N-1条小道，并且希望所有水龙头之间修建的道路，都要大于两个水龙头之前连接的所有小道(小道当然要是最短的了)。所以神COW们，帮那些OIER们计算一下吧，修建的那些道路总长度最短是多少，毕竟修建道路是要破费的~~

Input

本题为多组数据~

第一行t，表示有t组测试数据

对于每组数据

第一行N，表示水龙头的个数（当然也是OIER的个数）；

2到N行，每行三个整数X,Y,Z；表示水龙头X和水龙头Y有一条长度为Z的小道

Output

对于每组数据，输出一个整数，表示修建的所有道路总长度的最短值。

Sample Input

2

3

1 2 2

1 3 3

4

1 2 3

2 3 4

3 4 5

Sample Output

4

17

首先按边权值排序，然后从小到大加边，用并查集维护，每加一条边，对答案的贡献就是两个并查集大小乘上（权值+1），也就是乘法原理

很像Kruskal啊

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)	print(x/10);

	putchar(x%10+'0');

}

const int N=6e3;

int fa[N+10],size[N+10];

struct S1{

	int x,y,z;

	void insert(){x=read(),y=read(),z=read();}

	bool operator <(const S1 &a)const{return z<a.z;}

}A[N+10];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

int main(){

	for (int Data=read();Data;Data--){

		int n=read(),Ans=0;

		for (int i=1;i<=n;i++)	fa[i]=i,size[i]=1;

		for (int i=1;i<n;i++)	A[i].insert();

		sort(A+1,A+n);

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

			int x=find(A[i].x),y=find(A[i].y);

			if (x!=y){

				fa[x]=y;

				Ans+=(size[x]*size[y]-1)*(A[i].z+1);

				size[y]+=size[x];

			}

		}

		printf("%d\n",Ans);

	}

	return 0;

}

巴特西

[TYVJ1391]走廊泼水节

最新文章

热门文章