P8359 [SNOI2022] 垃圾回收

· · 题解

P8359 [SNOI2022] 垃圾回收

题意简述

给定一张无向图，然后进行 q 次操作（一次操作时间为 1），分为下面两种：

  1. 删除图中的一条边
  2. 删除图中所有的不与 1 号点连通的点（也就是只保留一号点的连通块

每个点都有一个权值。求出每个点的存活时间 \times 权值的和。

思路

先是在考场上现在想着怎么求出删点之后图的连通性，但后来发现删边操作极其难处理。然后，根据前期做题累积的教训，我将思路转化了一下，正难则反。

考虑将删边操作转化为加边操作。将输入的操作倒序枚举，那么之前的删边操作就转化为了加边操作。而且我们发现如果一直进行删边操作不进行删点操作的话是没什么影响的，只有进行了删边操作后再进行删点操作才有意义。所以我们将操作分组，每一组的结构都类似于 删边 / 删边 / 删边 ... 删点 ，也就是把删边的操作合并到后面的删点操作上，这样子我们在倒序枚举的时候，每遇见一个删除操作，就可以将正序要删的边加上，然后再把能和 1 号点新连通的点的权值加到一号点的那个连通块里。

然后我们发现我们转化为加边后，关心的只是与一号点连通的点的权值和，然后我们就可以不用建真图，加边操作就当作将连通块之间合并的操作就可以。所以我们使用并查集，并且维护每个连通块的权值和就 OK。

一定要注意整张图始终不连通的情况。那些与一号点不连通的会在第一次删点时被删掉，所以我们需要特别地处理那些点对答案的贡献。（本人被这个硬控 3h）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define endl '\n'

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}

const int N = 800010;

struct eg{
    ll a, b;
}edge[N];

int p[N];
ll w[N];

int find(int x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}

void add(int i){
    if(find(edge[i]. a) == find(edge[i]. b))return;
    w[find(edge[i]. b)] += w[find(edge[i]. a)];
    p[find(edge[i]. a)] = find(edge[i]. b);
    return;
}

bool st[N];
vector<ll>in[N];
ll tim[N];

signed main(){
    ll n = read(), m = read(), q = read();
    for(int i = 1; i <= n; i ++){
        p[i] = i;
    }
    for(int i = 1; i <= m; i ++){
        ll x = read(), y = read();
        edge[i] = {x, y};
    }
    queue<ll>que;
    int idx = 0;
    int sm = 0;
    for(int i = 1; i <= q; i ++){
        string s;
        cin >> s;
        if(s[0] == 'D'){
            ll mid = read();
            que. push(mid);
        }
        else{
            if(sm == 0)sm = i;
            if(que. empty())continue;
            idx ++;
            tim[idx] = i;
            while(que. size()){
                in[idx]. push_back(que. front());
                st[que. front()] = 1;
                que. pop();
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        w[i] = read();
    }
    for(int i = 1; i <= m; i ++){
        if(!st[i])add(i);
    }
    ll ans = w[find(1)] * ((q + 1) - tim[idx]);
    for(int i = idx; i >= 1; i --){
        for(auto it = in[i]. begin(); it != in[i]. end(); it ++)add(*it);
        ans += w[find(1)] * (tim[i] - tim[i - 1]);
    }
    set<ll>s;
    for(int i = 1; i <= n; i ++){
        if(find(i) != find(1))s. insert(find(i));
    }
    if(idx == 0)tim[1] = q + 1;
    for(auto it = s. begin(); it != s. end(); it ++){
        ans += sm * w[*it];
    }
    cout << ans;

    return 0;
}