Codeforces 786E ALT

点分治优化网络流建图,嘴巴优化理论复杂度。

题目大意

给出一棵 nnn 个节点的树与 mmm 条路径。你可以花费 111 的代价满足一条路径或一条边。如果一条路径包含的所有边都被满足,则这条路径也被满足。求使所有路径满足的最小代价并输出方案。

n≤20000n\le20000n20000m≤10000m\le10000m10000

题目链接

Codeforces 786E

题解

一个显然的想法是,我们建立一个二分图,一侧有 mmm 个点,每个点 xix_ixi 对应一条路径;另一侧有 nnn 个点,每个点 yiy_iyi 对应树上的一条边。如果第 iii 条路径覆盖了第 jjj 条边,就在二分图中对应连一条边 xi→yjx_i \rightarrow y_jxiyj。容易发现,这个二分图的最小点覆盖就是答案。二分图的最小点覆盖等于二分图的最大匹配,而最大匹配则可以建立源点、汇点后使用网络流解决。

然而在这个二分图中 ∣E∣=O(nm)|E|=O(nm)E=O(nm),边太多了,需要一些技巧来优化建图。我这里介绍我的一个使用了点分治的相对简单的方法(我看懂题意之后就想到了)。

容易发现,我们实际上要考虑的是优化 xix_ixi 向被第 iii 条路径覆盖的所有边连边的过程。而点分治可以做到将每条路径表示成预处理的 O(nlogn)O(n\log n)O(nlogn) 条路径中的两条,那么在这个问题中能否使用点分治优化建图呢?答案是肯定的。

考虑点分治过程中处理到一个重心为 uuu 的连通块的时刻,则我们实际上要考虑表示这个联通块中的每个其他点 vvvuuu 的路径,即对于每个 vvv,建一个点 zu,vz_{u,v}zu,v 能够(直接或间接)连向 uuuvvv 的路径上的所有边 eee 所对应的点 yey_eye。直接连这些边明显也是不行的。设以 uuu 为根时,点 vvv 的父亲是 fff,则 uuuvvv 的路径只比路径 uuufff 的路径多了一条边 e=f→ve = f\rightarrow ve=fv。因此,对于点 zu,vz_{u,v}zu,v,我们可以连边 zu,v→zu,fz_{u,v}\rightarrow z_{u,f}zu,vzu,f,容量为 ∞\infty;另连边 zu,v→yez_{u,v}\rightarrow y_{e}zu,vye,容量为 ∞\infty。容易发现,如果按这种方式连边,则 zu,vz_{u,v}zu,v 恰连向了 uuuvvv 的路径上的所有边所对应的点。

接下来的事情就很容易了。假设第 iii 条路径是 uuuvvv 的路径,设 u,vu,vu,v 在点分树中的最近公共祖先为 aaa,则我们连边 xi→za,ux_i\rightarrow z_{a,u}xiza,uxi→za,vx_i\rightarrow z_{a,v}xiza,v,容量均为 ∞\infty。则 xix_ixi 恰连向了 uuuvvv 的路径经过的所有边。另外对于每个点 xix_ixi,我们从附加源点 sss 向其连边 s→xis\rightarrow x_isxi,容量为 111;对于每个点 yjy_jyj,我们从其向附加汇点 ttt 连边 yj→ty_j\rightarrow tyjt,容量也为 111。可以看出这个新图的最大流与直接建图得到的最大流是相等的。而在这个新图中,∣V∣=∣E∣=O(m+nlogn)|V|=|E|=O(m+n\log n)V=E=O(m+nlogn)。使用 Dinic 算法求最大流,复杂度为 O((m+nlogn)3/2)O\left({(m+n\log n)^{3/2}}\right)O((m+nlogn)3/2)

这种建图方式其实可以进一步优化至 ∣V∣=O(m+n)|V|=O(m+n)V=O(m+n)。因为给出的路径个数只有 mmm,而每个 xix_ixi 最多只会向两个 zzz 连边,那么被用到的 zzz 的个数其实只有 O(m)O(m)O(m) 个。因此在点分治时,我们可以对一个联通块建立虚树来建图。这样便可以将图的总点数降低至 O(m+n)O(m+n)O(m+n)。然而这个做法会使代码复杂度增加很多。不管有没有人写反正我不想写

本题的官方题解给出的是一种 ∣V∣=O(m+nlogn)|V|=O(m+n\log n)V=O(m+nlogn)∣E∣=O((m+n)logn)|E|=O((m+n)\log n)E=O((m+n)logn) 的做法,而神犇 liu_cheng_ao 利用树剖和线段树得到了一个 ∣V∣=O(m+n)|V|=O(m+n)V=O(m+n)∣E∣=O(mlog2n+n)|E|=O\left(m\log^2n+n\right)E=O(mlog2n+n) 的做法(实测效率较高),有兴趣的话可以自行翻代码查看。

关于输出方案的话,只需要从源点 sss 开始延残量网络 DFS,则没有经过的 xix_ixi 与经过的 yjy_jyj 就是一个最小点覆盖。具体证明请自行搜索。

代码

#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

const int MAXN = 20031, MAXL = 16, INF = 0x3FFFFFFF, MAXS = MAXN * (MAXL + 2);

namespace F {
    int n = 0, s = n++, t = n++;

    struct E {
        int v, c, rv;
    };

    std::vector<E> g[MAXS];

    void ie(int u, int v, int c) {
        if (u == -1 || v == -1) return;
        g[u].push_back({v, c, g[v].size()}), g[v].push_back({u, 0, g[u].size() - 1});
    }

    int d[MAXS], cur[MAXS];

    bool bfs() {
        std::queue<int> q;
        std::fill(d, d + n, -1);
        for (d[s] = 0, q.push(s); !q.empty(); q.pop()) {
            int u = q.front();
            for (auto e : g[u])
                if (e.c && d[e.v] == -1) {
                    d[e.v] = d[u] + 1, q.push(e.v);
                    if (e.v == t) return 1;
                }
        }
        return 0;
    }

    int dfs(int u, int a) {
        if (u == t || a == 0) return a;
        int f = 0, z = 0;
        for (int &i = cur[u]; i < g[u].size(); i++) {
            auto &e = g[u][i];
            if (d[e.v] == d[u] + 1 && (z = dfs(e.v, std::min(e.c, a)))) {
                e.c -= z, g[e.v][e.rv].c += z;
                f += z, a -= z;
            }
            if (!a) break;
        }
        return f;
    }

    int dinic() {
        int ans = 0;
        for (; bfs(); std::fill(cur, cur + n, 0)) ans += dfs(s, INF);
        return ans;
    }

    bool vis[MAXS];

    void gans(int u) {
        vis[u] = 1;
        for (auto e : g[u]) if (e.c && !vis[e.v]) gans(e.v);
    }
}

std::vector<std::pair<int, int>> g[MAXN];
int id[MAXN], sz[MAXN], f[MAXN], x[MAXN][MAXL], l[MAXN];
bool vis[MAXN];

int gs(int u, int p) {
    sz[u] = 1;
    for (auto e : g[u]) if (!vis[e.first] && e.first != p) sz[u] += gs(e.first, u);
    return sz[u];
}

int ctrd(int u, int p, int hs) {
    for (auto e : g[u]) if (!vis[e.first] && e.first != p && sz[e.first] > hs) return ctrd(e.first, u, hs);
    return u;
}

void build(int u, int p, int ly) {
    for (auto e : g[u]) {
        int v = e.first;
        if (!vis[v] && v != p) {
            x[v][ly] = F::n++;
            F::ie(x[v][ly], x[u][ly], INF), F::ie(x[v][ly], e.second, INF);
            build(v, u, ly);
        }
    }
}

int dcomp(int u, int ly) {
    int ctr = ctrd(u, 0, gs(u, 0) / 2);
    vis[ctr] = 1;
    x[ctr][ly] = -1;
    build(ctr, 0, l[ctr] = ly);
    for (auto e : g[ctr]) if (!vis[e.first]) f[dcomp(e.first, ly + 1)] = ctr;
    return ctr;
}

int lca(int u, int v) {
    for (; u != v; u = f[u]) if (l[u] < l[v]) std::swap(u, v);
    return l[u];
}

int n = 0, m = 0;
int idc[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u = 0, v = 0; i < n; i++) {
        scanf("%d%d", &u, &v);
        F::ie(id[i] = F::n++, F::t, 1);
        g[u].push_back({v, id[i]}), g[v].push_back({u, id[i]});
    }
    dcomp(1, 0);
    for (int i = 1, u = 0, v = 0; i <= m; i++) {
        scanf("%d%d", &u, &v);
        int ly = lca(u, v);
        F::ie(F::s, idc[i] = F::n++, 1);
        F::ie(idc[i], x[u][ly], INF), F::ie(idc[i], x[v][ly], INF);
    }
    printf("%d\n", F::dinic());
    F::gans(F::s);
    std::vector<int> z;
    for (int i = 1; i <= m; i++) if (!F::vis[idc[i]]) z.push_back(i);
    printf("%d ", z.size());
    for (auto x : z) printf("%d ", x);
    puts("");
    z.clear();
    for (int i = 1; i < n; i++) if (F::vis[id[i]]) z.push_back(i);
    printf("%d ", z.size());
    for (auto x : z) printf("%d ", x);
    puts("");
    return 0;
}

2 thoughts on “Codeforces 786E ALT

  1. 重温神犇博客,看到这发现您的题目描述似乎有误?应该是当一条路径经过的所有边都被满足的时候才会自己满足?

发表评论

电子邮件地址不会被公开。 必填项已用*标注