Luogu6765

还是推荐用 LOJ 评测,可以评测全部的数据

LOJ3346

Description

给一个简单一些的题面

有一张 $n$ 个点 $m$ 条边的带权无向图, 均从 $0$ 开始编号.现在有 $Q$ 组询问,每次两个人从 $u,v$ 出发,要求这两个人不能同时在一个点上,也不能同时经过一条边.允许多次走一个点或者一条边.

现在要求最小化路径上的最大边权.

Sol

APIO2021来之前决定做一些 APIO 的真题来练练手

APIO 的题都是用实现函数类似于交互库的形式, 还是要提前适应

首先看到最小化最大这种东西,可以先试着往二分上靠.那么就二分这个答案最大权,每次两个点丢进去暴跳的途中判断就完事儿了.可能要注意下细节.应该可以拿到 Subtask3 的部分分

现在二分判定的瓶颈不在二分出答案上面,而是在判定答案时我是爆判的.考虑来优化这个过程.最简单的情形就是在一条链上面,这个两个人如果同时往中间跳时相遇,就跑不掉了.这样链的答案是 $-1$ . 菊花图的情况对应 Subtask2, 那么只需要判断一下起点和终点经不经过菊花根就可以了.

现在要解决的问题就是什么时候一定会有答案. 已知链无解,无解是因为必要同时经过同一边.但凡有一条别的出边能出去,就有可能有解. 假如现在有这么一条边能让它出去了,要再让他回来到达终点就必须有一条边引回.这样就是一个三元环.(这个过程可以多画画图)

解决了这个问题,二分的方法复杂度是 $O(Qn \log n)$ .可以通过 Subtask4

解决问题的关键又变成了二分不够优秀.考虑 Kruskal 重构树.可以用来解决这个问题. 在 Kruskal 重构树上, $u, v$ 路径上的最小被阀值限制的边权就是它们 lca 的点权.

还有一个问题就是做 Kruskal 的时候还要注意连通块是不是链的问题.可以这么解决,同时维护一个连通块的起点和终点,以及连通块的一个根.合并的时候注意,分情况讨论.

  1. 现在两个连通块要合并,不是链的话合并以后也不是
  2. 还不能合并:

    1. 有一个不是新的就不是
    2. 原来两个都是链,那么就看是不是两条链的端点连边,如果是的话就会连成一条链.

Code

Luogu 的不要加 swap.h 这一句

#include <bits/stdc++.h>
#include "swap.h"

const int SIZE = 3e5 + 5;

int num, idx, tim, n;
int head[SIZE], vis[SIZE], w[SIZE], st[SIZE], ed[SIZE], fa[SIZE], dfn[SIZE], root[SIZE], f[SIZE][21];

std::vector < int > chain[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];

struct E {
    int from, to, v;

    bool operator< (const E a) const {
        return v < a.v;
    }
} e[SIZE];

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void dfs(int u, int anc) {
    dfn[u] = ++ idx;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == anc) continue;
        f[v][0] = u, root[v] = !u ? 0 : root[u];
        for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
        // printf("from:%d to:%d\n", u, v);
        dfs(v, u);
    }
}

void init(int N, int M, std::vector < int > U, std::vector < int > V, std::vector < int > W) {
    int tot = 0; tim = N, n = N;
    for (int i = 1; i <= M; ++ i) e[i].from = U[i - 1] + 1, e[i].to = V[i - 1] + 1, e[i].v = W[i - 1];
    std::sort(e + 1, e + M + 1);
    for (int i = 1; i <= N; ++ i) fa[i] = i, st[i] = ed[i] = root[i] = i, chain[i].push_back(i);
    for (int i = 1; i <= M; ++ i) {
        int x = e[i].from, y = e[i].to;
        int fx = find(e[i].from), fy = find(e[i].to); tim = i + N;
        if (chain[fx].size() < chain[fy].size()) { std::swap(x, y); std::swap(fx, fy); }
        if (fx == fy) {
            if (!vis[fx]) {
                vis[fx] = 1;
                for (auto it: chain[fx]) addEdge(tim, it);
                root[fx] = tim;
            }    
        }
        else {
            if (vis[fx] || vis[fy]) {
                if (vis[fx]) addEdge(tim, root[fx]);
                else for (auto it: chain[fx]) addEdge(tim, it);
                if (vis[fy]) addEdge(tim, root[fy]);
                else for (auto it: chain[fy]) addEdge(tim, it);
                vis[fx] = 1, root[fx] = tim, fa[fy] = fx;
            }
            else {
                if ((x == st[fx] || x == ed[fx]) && (y == st[fy] || y == ed[fy])) {
                    st[fx] = x ^ st[fx] ^ ed[fx], ed[fx] = y ^ st[fy] ^ ed[fy];
                    for (auto it: chain[fy]) chain[fx].emplace_back(it);
                    fa[fy] = fx;
                }
                else {
                    vis[fx] = 1; 
                    for (auto it: chain[fx]) addEdge(tim, it);
                    for (auto it: chain[fy]) addEdge(tim, it);
                    fa[fy] = fx, root[fx] = tim;
                }
            }
        }
    }
    for (int i = N + M; i; -- i) {
        if (!dfn[i]) dfs(i, 0);
    }
    // for (int i = 1; i <= N + M; ++ i) {
    //     printf("from:%d ", i);
    //     for (int j = 1; j <= 5; ++ j) printf("%d ", f[i][j]);
    //     puts("");
    // }
}

int lca(int u, int v) {
    if (u == v) return u;
    if (root[u] != root[v]) return -1;
    if (dfn[u] > dfn[v]) std::swap(u, v);
    for (int i = 20; ~i; -- i) {
        if (dfn[f[v][i]] > dfn[u]) v = f[v][i];
    }
    return f[v][0];
}

int getMinimumFuelCapacity(int X, int Y) {
    ++ X, ++ Y;
    int anc = lca(X, Y);
    if (anc == -1) return -1;
    return e[anc - n].v;
}
最后修改:2021 年 08 月 20 日
如果觉得我的文章对你有用,请随意赞赏