solution-p8359

LXYYDS · 2022-07-01 00:16:44 · 题解

题意：

给定一个五香无向图。

每个节点 i 有两种属性 a_i 以及 alive_i。

其中 a_i 题目中给出， alive_i 初始值为 0。

对五香图进行以下两种操作：

删除一条边。
对于每个 ^{1.} 与起点（编号为 1 的节点）不连通， ^{2.} alive 值为 0 的点 i ，将 alive_i 的值改为当前时间戳（当前操作的编号）

共 q 种操作，编号为 1 \to q。

所有操作执行完后，将剩余的 alive 值为 0 的点的 alive 改为 q + 1。求：

\sum_{i=1}^na_i \cdot alive_i

暴力

显然我们有暴力做法：

对于每条边额外记录一个类型为 bool 的值，表示这条边的状态（ 0 表示未删除， 1 表示已删除）。

经过上述变换后，可以拿一半的分数。~~物美价廉，岂不美哉！~~

正解

对于暴力做法，我们将删边时间变为 O(1) ，改值时间则为 O(n)。

由此可见，改值操作时间过长，所以，我们希望优化。

观察数据范围可知，本题时间复杂度应为 O(n \cdot \log_2n) 或 O(n)。

感性理解，应为数据结构。

此时我们要有 逆向思维 。

删边等价于加边。

于是就有思路了：

我们将操作 1（删边）反向，改为加边。

那么处理加边的数据结构有哪些呢？并查集！

我们将上面的零散的思路组合一下，这道题的解法就出来了！

简略完整思路如下：

将所有没有删去的边保留下来，建立初始并查集。
倒序处理所有操作，对于删边操作，改为加边（用并查集维护），额外记录每个点所在并查集的 a_i 的总和 s_i ，对于一次合并，若两个集合有且仅有一个集合包含起点，则 ans+=s_i \cdot time 其中， time 表示时间戳，初值为 q + 1。
对于改值操作，修改时间戳。

一些细节：

图有可能本来就不连通（如样例 2 )操作之后还需要将剩下的点再做处理。

代码


#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Edge {
    long long x, y, d;
    bool b;
};
string S[400009];
Edge e[400009]; 
long long n, m, q, dele[400009], father[400009], cnt;
bool visit[400009];
unsigned long long ans, tim, ln, siz[400009], yua[400009];

long long get_father(long long x) {
    return x == father[x] ? x : father[x] = get_father(father[x]);
}

int main () {
    scanf("%lld%lld%lld", &n, &m, &q);
    for (register long long i = 1; i <= m; i ++) {
        scanf("%lld%lld", &e[i].x, &e[i].y);
        e[i].d = i;
        e[i].b = true;
    }

    for (register long long i = 1; i <= n; i ++) {
        if (visit[i])
            continue;
        ln += siz[i];
    }
    for (register long long i = 1; i <= q; i ++) {
        cin >> S[i];
        if (S[i] == "DELETE") {
            cin >> dele[i];
            e[dele[i]].b = false;
        }   
    }
    for (register long long i = 1; i <= n; i ++) {
        cin >> siz[i];
        yua[i] = siz[i];
    }

    for (register long long i = 1; i <= n; i ++) {
        father[i] = i;
    }
    for (register long long i = 1; i <= m; i ++) {
        if (e[i].b) {
            long long x = get_father(e[i].x), y = get_father(e[i].y);
            if (x == y)
                continue;
            if (x == 1) {
                siz[x] += siz[y];
                father[y] = x;
            }
            else {
                siz[y] += siz[x];
                father[x] = y;
            }
        }
    }
    tim = q + 1;
    ans = tim * siz[1];
    for (register long long i = q; i >= 1; i --) {
        if (S[i] == "GC") {
            tim = i;
        }
        else {
            long long x = get_father(e[dele[i]].x), y = get_father(e[dele[i]].y);
            if (x == y)
                continue;
            if (x == 1) {
                siz[x] += siz[y];
                ans += tim * siz[y];
                father[y] = x;
            }
            else if (y == 1) {
                siz[y] += siz[x];
                ans += tim * siz[x];
                father[x] = y;
            }
            else {
                siz[y] += siz[x];
                father[x] = y;
            }

        }
    }
    for (register long long i = 1; i <= n; i ++)
        if (get_father(i) != 1)
            ln += yua[i];
    printf("%llu\n", ans + tim * ln);
    return 0;
}