自动搬运

查看原文

来自洛谷，原作者为

	苏联小渣 believe in miracle.

搬运于2025-08-24 22:58:52，当前版本为作者最后更新于2024-05-21 20:44:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑没有修改的情况，套路地按照权值从大到小排序，倒序加边，每次加一个权值为 $v$ 的边就从这条边的起始点开始遍历未被遍历过的点（前提是起始点现在可从 $1$ 到达），然后此时遍历到的点的答案就是 $v$。

考虑有修改的情况，发现权值都很小，这其实我们对于每个值做。对于每个值 $v$，维护当前只保留 $\ge v$ 的边形成的子图 $G_v$，同时维护每个图中点到 $1$ 的可达情况，那么一个点 $x$ 目前的答案，就是一个最大的 $v$，使得在 $G_v$ 中 $x$ 是从 $1$ 可达的。

如果直接做的话需要支持删边、维护联通性，显然不好做；考虑把操作离线然后倒过来，就变成了加边。这样每次将权值 $d_x$ 增加 $y$ 影响的图只有 $y$ 个，对这些图暴力做即可。由于每次都是遍历未被遍历过的点，所以每个点只会被遍历一次，时间复杂度 $O(nd_i)$。

Code：

#include <bits/stdc++.h>
using namespace std;
#define N 100
int n, m, q, ans, pw[100010], dx[200010], dy[200010], mx[200010], out[200010], vis[105][100010];
const int mo = 998244353;
struct Graph{
	int p, h[100010];
	struct node{
		int x, y, next;
	}d[200010];
	void add(int x, int y){
		d[++p].y = y, d[p].next = h[x], h[x] = p;
	}
}G[105];
struct edge{
	int x, y, z;
}a[200010];
void dfs(int id, int x){
	vis[id][x] = 1;
	if (id > mx[x] && x != 1){
		ans = (ans - 1LL * pw[x] * mx[x] % mo + mo) % mo;
		ans = (ans + 1LL * pw[x] * id % mo) % mo;
		mx[x] = id;
	}
	for (int i=G[id].h[x]; i; i=G[id].d[i].next){
		int y = G[id].d[i].y;
		if (vis[id][y]) continue;
		dfs(id, y);
	}
}
int main(){
	scanf ("%d%d%d", &n, &m, &q);
	pw[0] = 1;
	for (int i=1; i<=n; i++){
		pw[i] = 2LL * pw[i-1] % mo; 
	}
	for (int i=1; i<=m; i++){
		scanf ("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
	}
	for (int i=1; i<=q; i++){
		scanf ("%d%d", &dx[i], &dy[i]);
		a[dx[i]].z -= dy[i];
	}
	for (int i=1; i<=m; i++){
		for (int j=1; j<=a[i].z; j++){
			G[j].add(a[i].x, a[i].y);
		}
	}
	for (int i=1; i<=N; i++){
		dfs(i, 1);
	}
	for (int i=q; i>=1; i--){
		out[i] = ans;
		for (int j=a[dx[i]].z+1; j<=a[dx[i]].z+dy[i]; j++){
			G[j].add(a[dx[i]].x, a[dx[i]].y);
			if (vis[j][a[dx[i]].x]) dfs(j, a[dx[i]].x);
		}
		a[dx[i]].z += dy[i];
	}
	for (int i=1; i<=q; i++){
		printf ("%d\n", out[i]);
	}
	return 0;
}