NOIP模拟 - 树

题目描述

给出一张n个点，m条边的无向图，摧毁每条边都需要一定的体力，并且花费的体力值各不相同，给定图中两个点x，y（x≠y），每当(x,y)之间存在路径，就需要不断摧毁当前图中花费体力最少的一条边，直到该路径不联通。他定义cost(x,y)为摧毁(x,y)之间路径花费的体力和。

他想要求出以下这个结果：

其中 i,j∈n，并且i＜j 。

输入格式

第一行两个整数 n，m ，表示点数和边数。

接下来 m 行，每行三个整数 x，y，z，表示 x 和 y 之间存在一条花费体力为 z 的无向边。

输出格式

输出一个整数表示所求结果。

样例数据 1

输入

6 7

1 2 10

2 3 2

4 3 5

6 3 15

3 5 4

4 5 3

2 6 6

输出

256

备注

数据范围

对 50% 的输入数据 ：1≤n≤100；1≤m≤1000

对 100% 的输入数据 ：1≤n,m≤100000；1≤z≤100000

题目分析

先考虑选定的两点，置图为空，把边按权值从大到小加入，每次都检查选定的两点是否连通，若加入的这条边将其联通了，也就说明要是这两点断开，需要把权值小于当前边的边和当前边删掉，也就是一个前缀和。

再换个思路，每次添加一条边，它会将两个联通块合并，也就是让联通块1的点与联通块2的点分开需要删掉权值小于等于当前边的边和当前边（需要预处理边权的前缀和），则这条边的贡献是sze[联通块1] * sze[联通块2] * sum[小于等于这条边的边的边权总和]。

code

#include<iostream>

#include<cstdio>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int N = 100000;

int n, m, anc[N + 5], sze[N + 5];

typedef long long ll;

ll sum[N + 5], ans;

struct node{

	int from, to, weight;

	node(){}

	node(int _x, int _y, int _c):from(_x), to(_y), weight(_c){}

}edges[N + 5];

inline int read(){

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

	for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

	if(ch == '-') f = -1, ch = getchar();

	for(; ch >= '0'&& ch <= '9'; ch = getchar())

		i = (i << 1) + (i << 3) + (ch - '0');

	return i * f;

}

inline void wr(ll x){

	if(x < 0) x = -x, putchar('-');

	if(x > 9) wr(x / 10);

	putchar(x % 10 + '0');

}

inline int getAnc(int x){

	return anc[x] == x ? x : (anc[x] = getAnc(anc[x]));

}

inline bool Larger(const node &a, const node &b){

	return a.weight > b.weight;

}

inline bool Smaller(const node &a, const node &b){

	return a.weight < b.weight;

}

int main(){

	n = read(), m = read();

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

		int x = read(), y = read(), w = read();

		edges[i] = node(x, y, w);

	}

	sort(edges + 1, edges + m + 1, Smaller);

	for(int i = 1; i <= m; i++) sum[i] = sum[i - 1] + edges[i].weight;

	sort(edges + 1, edges + m + 1, Larger);

	for(int i = 1; i <= n; i++) anc[i] = i, sze[i] = 1;

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

		int x = edges[i].from, y = edges[i].to;

		int fx = getAnc(x), fy = getAnc(y);

		if(fx != fy){

			ans = (ans + sze[fy] * sze[fx] * sum[m - i + 1]) % 1000000000;

			sze[fy] += sze[fx];

			anc[fx] = fy;

		}

	}

	wr(ans % 1000000000);

	return 0;

}