P7457

Macesuted · 2021-06-01 14:05:45 · 题解

点击此处以获得更佳阅读体验

题面

题意

给出 n 个点和 q 个操作，每个操作属于下面三个中的一种：

1. 在点 u,~v 之间加入一条边权为 d 的无向边。
2. 删除 u,~v 之间的边。
3. 询问 u,~v 之间的所有路径中最小值最大为多少。

保证任意时刻没有重边，n,~q \le 10^5,~0 \le d \le 10。

分析

发现边权 d 的取值范围很小，我们考虑枚举每一个可能的答案（0 \sim 10），然后找到答案为当前枚举数值的询问并标记。

由于题目中同时有加边和删边操作，删边时我们无法很好地维护区间最小值最大这一信息，所以考虑使用线段树按时间分治去掉删边操作。

输入时直接将每条边插入到线段树中，然后先在范围 0 \sim 10 之间枚举答案 ans，接着遍历一遍线段树，每次只插入边权 \le ans 的边，遇到含有询问的结点时判断已加入的边是否可让两点联通，如果联通则标记此询问答案为 ans 并且在之后的遍历中不再考虑。判断联通使用可撤销并查集即可。

代码

注意可能存在加边是 u,~v，删边是 v,~u 的情况，如果没有判断可能会拿到 94 分。输入时指定 u,~v 大小关系，或是使用无序数对保留边信息均可解决这一问题。

/**
 * @author Macesuted ([email protected])
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {

// fread

}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 200005

typedef pair<int, int> pii;

struct Edge {
    int x, y, dist;
};

vector<Edge> tree[maxn << 2];
map<pii, pii> S;
pii ask[maxn];
int answer[maxn], fa[maxn], siz[maxn];
bool vis[maxn];

void insert(int p, int l, int r, int ql, int qr, Edge edge) {
    if (ql <= l && r <= qr) return tree[p].push_back(edge);
    int mid = (l + r) >> 1;
    if (ql <= mid) insert(p << 1, l, mid, ql, qr, edge);
    if (qr > mid) insert(p << 1 | 1, mid + 1, r, ql, qr, edge);
    return;
}

stack<pii> rec;
int getfa(int p) { return fa[p] == p ? p : getfa(fa[p]); }
void insert(int x, int y) {
    x = getfa(x), y = getfa(y);
    if (x == y) return rec.push((pii){-1, -1});
    if (siz[x] < siz[y]) swap(x, y);
    fa[y] = x, siz[x] += siz[y];
    return rec.push((pii){x, y});
}
void rollback(void) {
    if (rec.top().first == -1 && rec.top().second == -1) return rec.pop();
    fa[rec.top().second] = rec.top().second, siz[rec.top().first] -= siz[rec.top().second];
    return rec.pop();
}
void dfs(int p, int l, int r, int lim) {
    for (vector<Edge>::iterator i = tree[p].begin(); i != tree[p].end(); i++)
        if (i->dist <= lim) insert(i->x, i->y);
    if (l == r && vis[l] && answer[l] == -1 && getfa(ask[l].first) == getfa(ask[l].second))
        answer[l] = lim;
    int mid = (l + r) >> 1;
    if (l != r) dfs(p << 1, l, mid, lim), dfs(p << 1 | 1, mid + 1, r, lim);
    for (vector<Edge>::iterator i = tree[p].begin(); i != tree[p].end(); i++)
        if (i->dist <= lim) rollback();
    return;
}

int main() {
    int n = read<int>(), q = read<int>();
    for (register int i = 1; i <= q; i++) {
        int opt = read<int>();
        if (opt == 0) {
            int x = read<int>(), y = read<int>(), dist = read<int>();
            if (x > y) swap(x, y);
            S[(pii){x, y}] = (pii){dist, i};
        } else if (opt == 1) {
            int x = read<int>(), y = read<int>();
            if (x > y) swap(x, y);
            insert(1, 1, q, S[(pii){x, y}].second, i, (Edge){x, y, S[(pii){x, y}].first});
            S.erase((pii){x, y});
        } else
            vis[i] = true, ask[i].first = read<int>(), ask[i].second = read<int>();
    }
    for (map<pii, pii>::iterator i = S.begin(); i != S.end(); i++)
        insert(1, 1, q, i->second.second, q, (Edge){i->first.first, i->first.second, i->second.first});
    memset(answer, -1, sizeof(answer));
    for (register int i = 0; i <= 10; i++) {
        for (register int j = 0; j < n; j++) fa[j] = j, siz[j] = 1;
        dfs(1, 1, q, i);
    }
    for (register int i = 1; i <= q; i++)
        if (vis[i]) write(answer[i]), putch('\n');
    return 0;
}