GMOJ J2471 【旅行】

Description

一个有 $n$ 个点 $m$ 条边的无向图，经过第 $i$ 条边需要 $c_i$ 元。你可以买一张通票，如果你花了 $W$ 元买通票，那么你可以通过边权不超过 $W$ 的所有边。有 $q$ 个询问，第 $i$ 个询问问你从点 $x_i$ 出发，用 $w_i$ 元最多能到多少个地方。

$$1 \leq n, q \leq 2 \times 10^5, 1 \leq m \leq 4 \times 10^5, 0 \leq w \leq 10^9$$

Solution

考虑如果你当前有 $w$ 元的话，肯定是买一张 $w$ 元的通票最优。

因为你如果买的是一张 $a$ 元的通票，再单独买了一张 $b$ 元的票的话，实际上你可以买一张 $(a + b)$ 元的通票，也能过掉 $b$ 元的这条边。

然后考虑将询问离线，然后问题就变成了不断加边，询问一个点所在连通块中的点的数量。

用并查集加一个计数数组即可做到。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxN 2000010
using namespace std;
struct Edge{ int x, y, c; } b[maxN];
struct Query{ int x, w, pos; } a[maxN];
int Ans[maxN], cnt[maxN], f[maxN];
bool cmpB (Edge A, Edge B)
{
	return A.c < B.c;
}
bool cmpA (Query A, Query B)
{
	return A.w < B.w;
}
int find (int x)
{
	if(x == f[x])
	{
		return x;
	}
	else
	{
		return f[x] = find(f[x]);
	}
}
int main ()
{
	int n = 0, m = 0, Q = 0;
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= m; i++)
	{
		scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].c);
	}
	sort(b + 1, b + m + 1, cmpB);
	scanf("%d", &Q);
	for(int i = 1;i <= Q; i++)
	{
		a[i].pos = i;
		scanf("%d %d", &a[i].x, &a[i].w);
	}
	sort(a + 1, a + Q + 1, cmpA);
	for(int i = 1;i <= n; i++)
	{
		f[i] = i, cnt[i] = 1;
	}
	int j = 1;
	for(int i = 1;i <= Q; i++)
	{
		while(b[j].c <= a[i].w && j <= m)
		{
			int x = b[j].x, y = b[j].y;
			int tx = find(x), ty = find(y);
			if(tx != ty)
			{
				f[ty] = tx;
				cnt[tx] += cnt[ty];
			}
			j++;
		}
		Ans[a[i].pos] = cnt[find(a[i].x)];
	}
	for(int i = 1;i <= Q; i++)
	{
		printf("%d\n", Ans[i]);
	}
	return 0;
}