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

发表于 分类于 阅读次数： Valine：

题目链接（UOJ）

题意

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

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

\(n \le 10^5,m \le 3\times 10^5, k \le 20\)，时间限制：$3 $

分析

暴力

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

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

优化

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

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

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

实现

处理一定存在的边

1
2
3
4
5
6
7
8
9
10
11
12
13

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); // 专门记录旧边的并查集
    }
}

缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)];
    }
}

枚举所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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)); // 统计当前树的收益
    }
}

统计答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#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;
}