【题解】P3639 [APIO2013]道路费用

发表于 2021-11-14 分类于信息学阅读次数： 20 Valine：

题意

一个 $n$ 个结点的无向图，有 $m$ 条老边已经存在，给定起点、终点、权值，保证权值互不相同且此时图已经联通。还有 $k$ 条新边是G老板的，给定起点、终点，权值由G老板指定。

在G老板指定完权值后，在图的最小生成树上，结点 $i$ 上有 $p_{i}$ 个人要从结点 $i$ 去结点 $1$ （只能走最小生成树上的边）。每个人如果路过新边就要给G老板交权值那么多钱。求G老板最多赚多少。

$n \leq 10^{5}, m \leq 3 \times 10^{5}, k \leq 20$ ，时间限制： $3$

分析

暴力

发现 $k$ 很小，可以 $2^{k}$ 枚举每条边取或不取。之后跑 $Kruskal$ ，考虑如何求新边权值。对于不在 $MST$ 上的权值为 $w$ 的老边 $u \to v$ ， $MST$ 上 $u$ 到 $v$ 的路径上所有边的边权都 $\leq w$ 。考虑暴力爬 $(u, v)$ 这条链，权值对 $w$ 取 $min$ 。

整体复杂度 $O (m \times \log m + 2^{k} \times m^{2})$

优化

先加入所有新边，然后加旧边直到图联通。这里添加的旧边是一定会出现在最后的 $MST$ 里的。这些旧边被新边分成了 $k + 1$ 个连通块，可以缩成 $k + 1$ 个点。还有另外 $k$ 条旧边可以让这些连通块联通，这些边可能会出现在最后的 $MST$ 中。

于是我们每次 $2^{k}$ 枚举情况后只用再在 $k$ 条边中跑 $Kruskal$ ，树的大小只有 $2 \times k$ 。

整体复杂度 $O (m \times \log m + 2^{k} \times k^{2})$

实现

处理一定存在的边


void kruskal1() {
    for (int i = 1; i <= k; i++) {
        sAll.merge(edNew[i].u, edNew[i].v); // 先将所有新边加入
    }
    sort(edOld + 1, edOld + m + 1);
    for (int i = 1; i <= m; i++) {
        if (sAll.find(edOld[i].u) == sAll.find(edOld[i].v)) continue;
        sAll.merge(edOld[i].u, edOld[i].v);
        sOld.merge(edOld[i].u, edOld[i].v); // 专门记录旧边的并查集
    }
}

缩点

void redu() { //缩点
    for (int i = 1; i <= n; i++) { // 有多少个不同的并查集就有多少个连通块
        if (sOld.find(i) == i) id[i] = ++cntCon;
    }
    rt = id[sOld.find(1)]; // 记录缩点后树的根
    sAll = sOld;
    for (int i = 1; i <= n; i++) pCon[id[sOld.find(i)]] += p[i]; // 每个联通块的总人数
    for (int i = 1; i <= m; i++) {
        if (sOld.find(edOld[i].u) == sOld.find(edOld[i].v)) continue;
        sOld.merge(edOld[i].u, edOld[i].v);
        edCot[++cntCot] = edOld[i]; // 记录用来联通联通块的边
    }

    for (int i = 1; i <= k; i++) { // 更新原来的编号为缩点后的编号
        edNew[i].u = id[sAll.find(edNew[i].u)];
        edNew[i].v = id[sAll.find(edNew[i].v)];
    }
    for (int i = 1; i <= k; i++) {
        edCot[i].u = id[sAll.find(edCot[i].u)];
        edCot[i].v = id[sAll.find(edCot[i].v)];
    }
}

枚举所有情况

void sol() { // 枚举
    for (int sta = 0; sta < (1 << k); sta++) {
        bool ex = false;
        tmp = 0;
        for (int i = 1; i <= cntCon; i++) { // 初始化
            minn[i] = inf;
            head[i] = 0;
            sTmp.fa[i] = i;
        }
        for (int i = 1; i <= k; i++) {
            if (!(sta & (1 << (i - 1)))) continue;
            if (sTmp.find(edNew[i].u) == sTmp.find(edNew[i].v)) { // 加新边
                ex = true;
                break;
            }
            sTmp.merge(edNew[i].u, edNew[i].v);
            add(edNew[i].u, edNew[i].v);
            add(edNew[i].v, edNew[i].u);
        }
        if (ex) continue;
        for (int i = 1; i <= cntCot; i++) { // 连可能的旧边
            if (sTmp.find(edCot[i].u) == sTmp.find(edCot[i].v)) continue;
            sTmp.merge(edCot[i].u, edCot[i].v);
            add(edCot[i].u, edCot[i].v);
            add(edCot[i].v, edCot[i].u);
        }
        ans = max(ans, getsum(sta)); // 统计当前树的收益
    }
}

统计答案

ll getsum(int sta) {
    dfs(rt, 0); // 在MST上处理出人数和父亲
    for (int i = 1; i <= cntCot; i++) { // 暴力爬链，计算权值
        int x = edCot[i].u, y = edCot[i].v;
        ll val = edCot[i].w;
        while (x != y) {
            if (dep[x] < dep[y]) swap(x, y);
            minn[x] = min(minn[x], val); // minn记到深度较深的点上
            x = fa[x];
        }
    }
    ll sum = 0;
    for (int i = 1; i <= k; i++) {
        if (!(sta & (1 << (i - 1)))) continue;
        int x = edNew[i].u, y = edNew[i].v;
        if (dep[x] < dep[y]) swap(x, y);
        sum += minn[x] * siz[x]; // 统计答案
    }
    return sum;
}

完整代码

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const ll N = 3000005, inf = 1e18;
int n, m, k, cntCot, cntCon, rt;
ll p[N], id[N], pCon[N], siz[N], minn[N], dep[N], fa[N], ans;

struct edge {
    int u, v;
    ll w;

    bool operator<(const edge &x) const {
        return w < x.w;
    }
} edNew[N], edOld[N], edCot[N];

struct uSet {
    int fa[N];

    void init() {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }

    int find(int x) {
        if (x != fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) fa[x] = y;
    }
} sAll, sOld, sTmp;

struct node {
    int to, nxt;
} e[N << 1];

int head[N], tmp;

void add(int x, int y) {
    e[++tmp].to = y;
    e[tmp].nxt = head[x];
    head[x] = tmp;
}

void dfs(int x, int fath) {
    fa[x] = fath;
    dep[x] = dep[fath] + 1;
    siz[x] = pCon[x];
    for (int i = head[x]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fath) continue;
        dfs(v, x);
        siz[x] += siz[v];
    }
}

void readIn() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    sAll.init();
    sOld.init();
    sTmp.init();
    for (int i = 1; i <= m; i++) {
        cin >> edOld[i].u >> edOld[i].v >> edOld[i].w;
    }
    for (int i = 1; i <= k; i++) {
        cin >> edNew[i].u >> edNew[i].v;
    }
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
}

void kruskal1() {
    for (int i = 1; i <= k; i++) {
        sAll.merge(edNew[i].u, edNew[i].v); // 先将所有新边加入
    }
    sort(edOld + 1, edOld + m + 1);
    for (int i = 1; i <= m; i++) {
        if (sAll.find(edOld[i].u) == sAll.find(edOld[i].v)) continue;
        sAll.merge(edOld[i].u, edOld[i].v);
        sOld.merge(edOld[i].u, edOld[i].v); // 专门记录旧边的并查集
    }
}

void redu() { //缩点
    for (int i = 1; i <= n; i++) { // 有多少个不同的并查集就有多少个连通块
        if (sOld.find(i) == i) id[i] = ++cntCon;
    }
    rt = id[sOld.find(1)]; // 记录缩点后树的根
    sAll = sOld;
    for (int i = 1; i <= n; i++) pCon[id[sOld.find(i)]] += p[i]; // 每个联通块的总人数
    for (int i = 1; i <= m; i++) {
        if (sOld.find(edOld[i].u) == sOld.find(edOld[i].v)) continue;
        sOld.merge(edOld[i].u, edOld[i].v);
        edCot[++cntCot] = edOld[i]; // 记录用来联通联通块的边
    }

    for (int i = 1; i <= k; i++) { // 更新原来的编号为缩点后的编号
        edNew[i].u = id[sAll.find(edNew[i].u)];
        edNew[i].v = id[sAll.find(edNew[i].v)];
    }
    for (int i = 1; i <= k; i++) {
        edCot[i].u = id[sAll.find(edCot[i].u)];
        edCot[i].v = id[sAll.find(edCot[i].v)];
    }
}

ll getsum(int sta) {
    dfs(rt, 0); // 在MST上处理出人数和父亲
    for (int i = 1; i <= cntCot; i++) { // 暴力爬链，计算权值
        int x = edCot[i].u, y = edCot[i].v;
        ll val = edCot[i].w;
        while (x != y) {
            if (dep[x] < dep[y]) swap(x, y);
            minn[x] = min(minn[x], val); // minn记到深度较深的点上
            x = fa[x];
        }
    }
    ll sum = 0;
    for (int i = 1; i <= k; i++) {
        if (!(sta & (1 << (i - 1)))) continue;
        int x = edNew[i].u, y = edNew[i].v;
        if (dep[x] < dep[y]) swap(x, y);
        sum += minn[x] * siz[x]; // 统计答案
    }
    return sum;
}

void sol() { // 枚举
    for (int sta = 0; sta < (1 << k); sta++) {
        bool ex = false;
        tmp = 0;
        for (int i = 1; i <= cntCon; i++) { // 初始化
            minn[i] = inf;
            head[i] = 0;
            sTmp.fa[i] = i;
        }
        for (int i = 1; i <= k; i++) {
            if (!(sta & (1 << (i - 1)))) continue;
            if (sTmp.find(edNew[i].u) == sTmp.find(edNew[i].v)) { // 加新边
                ex = true;
                break;
            }
            sTmp.merge(edNew[i].u, edNew[i].v);
            add(edNew[i].u, edNew[i].v);
            add(edNew[i].v, edNew[i].u);
        }
        if (ex) continue;
        for (int i = 1; i <= cntCot; i++) { // 连可能的旧边
            if (sTmp.find(edCot[i].u) == sTmp.find(edCot[i].v)) continue;
            sTmp.merge(edCot[i].u, edCot[i].v);
            add(edCot[i].u, edCot[i].v);
            add(edCot[i].v, edCot[i].u);
        }
        ans = max(ans, getsum(sta)); // 统计当前树的收益
    }
}

int main() {
    readIn();
    kruskal1();
    redu();
    sol();
    cout << ans << endl;
    return 0;
}