题解 P6765 【[APIO2020]交换城市】

syksykCCC · 2020-09-09 23:34:28 · 题解

Subtask 1

「每个城市至多是两条道路的一个端点」说明只存在两种情况：一是整张图构成一条链，这时答案显然始终为 -1；二是整张图构成一个环，这时答案显然为 \max W，因为唯一可能的错车方法就是两辆车分别从两边走，那正好遍历了图上的每一条边，答案为全局最大值。

Subtask 2

菊花图的处理方法也很简单，分为两种情况：

一是 X = 0, Y \ne 0 ，那么答案为连接 (0, Y) 的边以及其他边中最小的和次小的这三边的 \max（图左）。

二是 X \ne 0, Y \ne 0，那么答案为连接 (0, X) 的边，连接 (0, Y) 的边，以及其他边中最小的这三边的 \max（图右）。

Subtask 3

我们可以用一个类似 Dijkstra 的算法来尝试解决这个部分分。

用 cost_{A, B} 来表示有两辆车分别是 X \to A, Y \to B 时所需要的最小边权。初始除了 cost_{X, Y} \gets 0 外其他均为 +\infty。显然答案为 cost_{Y, X}。

比如现在我们已经有 cost_{A, B} 的值了，我们可以尝试把位于 A 的车移动到一个相邻的点 C (C \ne B)，这条连接 (A, C) 的边边权为 D。然后我们就可以更新 cost_{C, B} \gets \min(cost_{C, B}, \max(cost_{A, B}, D))。同样我们可以尝试把位于 B 的车移动到一个相邻的点，全部更新结束就可以得到答案了。

时间复杂度 O(Q \times N \times (N+M) \times \log (N^2))。

Subtask 4

回想 Subtask 1, 2，我们可以得到，两个城市可以互相到达当且仅当下面两个条件之一成立：

• 构成环；
• 某结点度数 \ge 3。

总结一下，就是所在连通块不为链即可。

由于本题求的是瓶颈边，考虑利用 Kruskal 算法求最小生成树的过程。

我们按照 W 从低到高插入每条边，动态维护一个 \text{nch}_u (not a chain) 表示以 u 为代表元的连通块是否脱离的链的形态。下面记 \operatorname{Find}(u) 表示寻找包含 u 的连通块的代表元，也就是并查集的找父亲操作。

当我们插入某一条边后 \operatorname{Find}(X) = \operatorname{Find}(Y) = Z（X, Y 连通）且 \text{nch}_Z = 1（该连通块脱离链的形态），那么我们就可以停止操作，答案即为这条边的边权。

问题在于 \text{nch}_u 怎么维护。比如现在插入的边是 (A, B)，首先 deg_A \gets deg_A + 1, deg_B \gets deg_B + 1，那么 \text{nch}_u = 1 当且仅当下面五者有一个成立：

如果所有边都插入了终止条件还是不满足，答案为 -1。

时间复杂度 O(M \log M + Q \times M \times \alpha(N))。

subtask 5

图的形态是一棵树，那么我们就不用考虑构成环的情况了。

用 cost_u 表示从 u 出发，找到一个可以错车的三叉路口，走过的最大边权最小是多少。初始时，如果 deg_x \ge 3，则 cost_x = 和 x 连接的第三小的边权；否则 cost_x = \infty。

如果有一条边连接了 (A, B)，边权为 C，那么可以得到 DP 式子 cost_A \gets \min(cost_A, \max(cost_B, C)), cost_B \gets \min(cost_B, \max(cost_A, C)) 。DP 的顺序很套路，可以从叶子结点一路上传到根，再从根传播到各个子节点。

最终，答案就是 \max(X \to Y 路径上的最大边权, cost_X)。前面那部分可以直接倍增维护一下。

时间复杂度 O(N \log N + Q \log N)。

subtask 6

Subtask 4 的做法是比较靠谱的，可惜它需要每次询问都做一次 Kruskal。所以，我们可以尝试使用 Kruskal 重构树的思路。

普通的 Kruskal 重构树可以回答 X, Y 连通之后的瓶颈边权，现在我们不是想要 X, Y 简单连通，而是不呈现链状连通。可以改造一下 Kruskal 重构树，使得它成为一棵多叉树，但依然满足 \operatorname{LCA}(X, Y) 的权值就是答案。

所以，在 \text{nch}_u = 1 之前，用一个数组 \text{pnt}_u 来表示 u 所在连通块内点的编号，而在 \text{nch}_u = 1 之后，把 \text{pnt}_u 当中的每一个元素都连到父结点上。\text{pnt} 可以通过启发式合并来保证复杂度。（感谢这篇题解的优秀思路）

比如现在加入一条边 (A, B)，分如下情况：

• 如果之前 A, B 已经连通且是链，那么加上这条边就不再是链了，打上标记，同时在 Kruskal 重构树上连边；
• 如果原来 A, B 两个连通块有至少一个不是链，那么新连通块也一定不是链，打上标记，同时在 Kruskal 重构树上连边；
• 如果原来 A, B 两个连通块都是链，那么新连通块是不是链取决于连边是不是在端点之间进行的。可以维护 s_u 和 t_u 表示 u 为代表元的链的端点，那么这里就很好判断：
  • 如果不是在端点进行的，那么加上这条边就不再是链了，打上标记，同时在 Kruskal 重构树上连边；
  • 如果是在端点进行的，那么加上这条边依然是链，更新 s 和 t，同时合并 \text{pnt}。

时间复杂度 O(N \log N + Q \log N)。

代码中结点编号从 1 开始。

#include "swap.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std; 
const int MAXN = 500005;
int n, m, cnt, f[20][MAXN], dep[MAXN], s[MAXN], t[MAXN], rt[MAXN];
vector<int> pnt[MAXN], tr[MAXN];
bool nch[MAXN];
struct disjoint_sets_union
{
    int fa[MAXN];
    void init() { for(int i = 1; i <= n; i++) fa[i] = i; }
    int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }
} dsu;
struct edge
{
    int u, v, w;
    bool operator < (const edge &oth) const { return w < oth.w; }
} e[MAXN];

void DFS(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    rt[u] = fa ? rt[fa] : u;
    f[0][u] = fa;
    for(int k = 1; k <= 19; k++) f[k][u] = f[k - 1][f[k - 1][u]];
    for(int v : tr[u]) DFS(v, u);
}

int LCA(int u, int v)
{
    if(rt[u] != rt[v]) return -1;
    if(dep[u] < dep[v]) swap(u, v);
    for(int k = 19; ~k; k--)
    {
        if(dep[f[k][u]] < dep[v]) continue;
        u = f[k][u];
    }
    if(u == v) return u;
    for(int k = 19; ~k; k--)
    {
        if(f[k][u] == f[k][v]) continue;
        u = f[k][u]; v = f[k][v];
    }
    return f[0][u];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) 
{
    n = N; m = M;
    for(int i = 0; i < m; i++) e[++cnt] = (edge){U[i] + 1, V[i] + 1, W[i]};
    sort(e + 1, e + m + 1);
    dsu.init();
    for(int i = 1; i <= n; i++) { s[i] = t[i] = rt[i] = i; pnt[i].push_back(i); }
    for(int i = 1; i <= m; i++)
    {
        int u = e[i].u, v = e[i].v;
        int fau = dsu.find(u), fav = dsu.find(v);
        if(pnt[fau].size() < pnt[fav].size()) { swap(u, v); swap(fau, fav); }
        int cur = i + n;
        if(fau == fav)
        {
            if(!nch[fau])
            {
                nch[fau] = true;
                for(int k : pnt[fau]) tr[cur].push_back(k);
                pnt[fau].clear();
                rt[fau] = cur;
            }
        }
        else
        {
            if(nch[fau] || nch[fav])
            {
                if(nch[fau]) tr[cur].push_back(rt[fau]);
                else for(int k : pnt[fau]) tr[cur].push_back(k);
                if(nch[fav]) tr[cur].push_back(rt[fav]);
                else for(int k : pnt[fav]) tr[cur].push_back(k);
                pnt[fau].clear(); pnt[fav].clear();
                nch[fau] = true;
                rt[fau] = cur;
                dsu.fa[fav] = fau;
            }
            else
            {
                if((u == s[fau] || u == t[fau]) && (v == s[fav] || v == t[fav]))
                {
                    s[fau] = u ^ s[fau] ^ t[fau]; t[fau] = v ^ s[fav] ^ t[fav];
                    for(int k : pnt[fav]) pnt[fau].push_back(k);
                    pnt[fav].clear();
                    dsu.fa[fav] = fau;
                }
                else
                {
                    nch[fau] = true;
                    for(int k : pnt[fau]) tr[cur].push_back(k);
                    for(int k : pnt[fav]) tr[cur].push_back(k);
                    pnt[fau].clear(); pnt[fav].clear();
                    rt[fau] = cur;
                    dsu.fa[fav] = fau;
                }
            }
        }
    }
    for(int i = n + m; i; i--)
        if(!dep[i]) DFS(i, 0);
}

int getMinimumFuelCapacity(int X, int Y)
{
    int a = LCA(X + 1, Y + 1);
    if(a == -1) return -1;
    return e[a - n].w;
}