列表

详情


NC25450. HRY and tree

描述

In 9102, HRY was elected as the director of the GDCPC Metro Bureau. In his work, he needs to use his knowledge to solve some problems.
The subway line of GDCPC can be regarded as a connected graph composed of n points and n-1 edges. The edge weight represents the distance between two points. The weight of the path between two different points is defined as the maximum value of the edge weights of all edges on the simple path between them. Now HRY needs to know the sum of the weights of all pairs of points (obviously there are kinds), because he is busy, so he wants you, a JBer, to helped him calculate it.

输入描述

The first line of the input file contains a positive integer T, indicating the number of test cases.
Each case has n lines. The first line is a positive integer n, indicating the number of points; the next n-1 lines each line contains three positive integers u, v, w, indicating that there is an edge between u and v, and the weight of this edge is w.
It is guaranteed that the input forms a tree.

The sum of n does not exceed 2000000.

输出描述

For each test case, output a line of a positive integer representing the sum of the weights of all paths.

示例1

输入:

2
3
1 2 1
2 3 2
4
1 2 1
1 3 2
1 4 3

输出:

5
14

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 1169ms, 内存消耗: 20060K, 提交时间: 2019-04-27 20:08:04

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
const int N=1e6+10;
int T,n,fa[N],size[N];
struct edge{
	int x,y,z;
	bool operator < (const edge &rhs) const {
		return z<rhs.z;
	}
}e[N];

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

int main()
{
	int T; cin>>T;
	while (T--) {
		scanf("%d",&n);
		for (int i=1;i<n;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
		sort(e+1,e+n);
		for (int i=1;i<=n;i++) fa[i]=i,size[i]=1;
		uLL ans=0;
		for (int i=1;i<n;i++) {
			int fx=getfa(e[i].x),fy=getfa(e[i].y);
			if (fx==fy) continue;
			ans+=(uLL)e[i].z*size[fx]*size[fy];
			size[fx]+=size[fy];
			fa[fy]=fx;
		}
		printf("%llu\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1843ms, 内存消耗: 63580K, 提交时间: 2019-05-02 16:54:24

#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}a[1000005];
int cmp(node x,node y){
	return x.w<y.w;
}
int fa[1000005],si[1000005];
int find(int x){
	if(x!=fa[x])
		return fa[x]=find(fa[x]);
	return fa[x];
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			fa[i]=i,si[i]=1;
		for(int i=1;i<n;i++)
			scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
		sort(a+1,a+n,cmp);
		unsigned long long ans=0;
		for(int i=1;i<n;i++){
			int fx=find(a[i].u),fy=find(a[i].v);
			if(fx==fy)
				continue;
			ans+=(unsigned long long)a[i].w*si[fx]*si[fy];
			si[fx]+=si[fy];
			fa[fy]=fx; 
		}
		printf("%llu\n",ans);
	}
}

上一题