[题解] P10525 [XJTUPC2024] 图上操作

苏联小渣 · 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;
}