题目描述
( ext{Tom}) 热爱出毒瘤题，但这次他似乎出了一个并不毒瘤的题。
给定一张 (N) 个点 (M) 条无向边的图，每条边有边权 (w)。定义一个连通块的大小为该连通块内所有边权的和。
然后进行 (K) 组询问。每次询问在由所有边权不超过 (X_i) 的边构成的新的生成子图中连通块的大小的最大值。
输入格式
第 (1) 行 (3) 个整数 (n,m,k) 表示图有 (n) 个点，(m) 条边。有 k 组询问。
第 (2) 行到第 (m + 1) 行每行三个正整数 (u，v，w，)表示点 (u) 和点 (v) 之间有一条边权为 (w) 的边。
第 (m + 1) 行到第 (m + k) 行每行一个整数 (x)，表示在这次询问中，只能使用边权不超过 (w) 的边。
可能存在重边，但不存在自环。
输出格式
(K) 行，对于每组询问输出一次答案。
样例
input1
5 5 3
1 2 5
2 3 6
3 4 4
3 5 2
4 5 3
7
5
3
output1
20
9
5
数据规模和限制
对于全部测试数据，满足 (N,M,K leq 100000)，(W leq1000)
| 测试点 | N | M | K |
|---|---|---|---|
| (1) | (leq 10) | (leq 10) | (leq 10) |
| (2 sim 3) | (leq 1000) | (leq 1000) | (leq 1000) |
| (4 sim 5) | (leq 1000) | (leq 1000) | (leq 100000) |
| (6 sim 10) | (leq 100000) | (leq 100000) | (leq 100000) |
思路
并查集。
将询问离线。从对边权的限制由小到大处理，这样就转化成了不断往一个图中加边，询问你加了多少遍之后最大的连通块的大小。
Code
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 100001
typedef int ll;
inline void read(ll &T) {
ll x = 0;
bool f = 0;
char c = getchar();
while(c < '0' || c > '9') {
if (c == '-') f = !f;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
T = f ? -x : x;
}
inline void write(ll x) {
if (x < 0) putchar('-'), write(-x);
else {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
}
int n, m, k;
ll ub[MAXN], ans[MAXN];
int fa[MAXN], size[MAXN];
struct P {
int u, v;
ll w;
friend bool operator < (P x, P y) {
return x.w < y.w;
}
}a[MAXN];
struct query {
int w, num;
friend bool operator < (query x, query y) {
return x.w < y.w;
}
}q[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Union(int x, int y) {
if (x > y) std::swap(x, y);
fa[y] = x;
}
ll max(ll a, ll b) { return a > b ? a : b; }
int main() {
//freopen("Graph.in", "r", stdin);
//freopen("Graph.out", "w", stdout);
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &a[i].u, &a[i].v);
read(a[i].w);
}
std::sort(a + 1, a + m + 1);
for (int i = 1; i <= k; ++i) {
scanf("%d", &q[i].w);
q[i].num = i;
}
std::sort(q + 1, q + k + 1);
int now = 1; ll maxx = 0;
for (int i = 1; i <= k; ++i) {
while(q[i].w >= a[now].w && now <= m) {
int rootx = find(a[now].u), rooty = find(a[now].v);
if (rootx != rooty) Union(rootx, rooty);
if (rootx < rooty) {
ub[rootx] += a[now].w;
ub[rootx] += ub[rooty];
ub[rooty] = 0;
maxx = max(maxx, ub[rootx]);
}
else {
ub[rooty] += a[now].w;
if (rootx != rooty) {
ub[rooty] += ub[rootx];
ub[rootx] = 0;
}
maxx = max(maxx, ub[rooty]);
}
++now;
}
ans[q[i].num] = maxx;
}
for (int i = 1; i <= k; ++i) write(ans[i]), puts("");
fclose(stdin), fclose(stdout);
return 0;
}