写在前面

整理了一份最小生成树算法板子

题目 C - 掌握魔法の东东 I

东东在老家农村无聊,想种田。农田有$ n$ 块,编号从 1~nn。种田要灌氵
众所周知东东是一个魔法师,他可以消耗一定的 MP 在一块田上施展魔法,使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门,使得这块田引用那块有水的田的水。 (1n3e2)(1 \le n \le 3e2)
黄河之水天上来的消耗是WiW_iii 是农田编号 (1Wi1e5)(1 \le W_i \le 1e5)
建立传送门的消耗是 PijP_{ij}iijj是农田编号 (1Pij1e5,Pij=Pji,Pii=0)(1 \le P_{ij} \le 1e5, P_{ij} = P_{ji}, P_{ii} =0)
东东为所有的田灌氵的最小消耗

input

第1行:一个数nn
第2行到第n+1n+1行:数wiw_i
n+2n+2行到第2n+12n+1行:矩阵即pijp_{ij}矩阵

output

东东最小消耗的MP值

sample input

1
2
3
4
5
6
7
8
9
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output

1
9

Kruskal

复杂度O(mlogm)O(mlogm)

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
const int MAXN = 3e2 + 7;
int par[MAXN];
struct re {
int x, y, w;
bool operator<(const re& a) const { return w < a.w; }
} v[MAXN * MAXN];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
int n;
cin >> n;
int cnt = 1;
for (int i = 1; i <= n; i++) {
v[cnt].x = 0;
v[cnt].y = i;
cin >> v[cnt].w;
++cnt;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int w = get_num();
if (i == j) continue;
v[cnt].x = i;
v[cnt].y = j;
v[cnt].w = w;
cnt++;
}
}
sort(v + 1, v + cnt);
int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) par[i] = i;
for (int i = 1; i < cnt; i++) {
if (sum == n) break;
if (find(v[i].x) != find(v[i].y)) {
ans += v[i].w;
par[find(v[i].x)] = find(v[i].y);
sum++;
}
}
cout << ans;
return 0;
}

Prim(Dijkstra)

复杂度O(n2)O(n^2)

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
const int MAXN = 3e2 + 7;
int v[MAXN][MAXN], vis[MAXN], d[MAXN];
int main() {
int n;
n = get_num();
for (int i = 1; i <= n; i++) {
v[0][i] = v[i][0] = get_num();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
v[i][j] = get_num();
}
}
for (int i = 0; i <= n; i++) {
vis[i] = 0;
d[i] = 1e9;
}
d[0] = 0;
int ans = 0;
for (int i = 0; i <= n; i++) {
int sum = 1e9, k;
for (int i = 0; i <= n; i++) {
if (!vis[i] && d[i] < sum) {
sum = d[i];
k = i;
}
}
ans += d[k];
vis[k] = 1;
for (int i = 0; i <= n; i++) {
d[i] = min(d[i], v[k][i]);
}
}
cout << ans;
return 0;
}

堆优化的Prim

复杂度O((m+n)logn)O((m+n)logn),若采用邻接矩阵存图时间复杂度为O(nlogn)O(nlogn)

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
const int MAXN = 3e2 + 7;
int v[MAXN][MAXN], vis[MAXN], d[MAXN];
struct re {
int d, w;
bool operator<(const re &a) const { return w > a.w; }
};
priority_queue<re> Q;
int main() {
int n;
n = get_num();
for (int i = 1; i <= n; i++) {
v[0][i] = v[i][0] = get_num();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
v[i][j] = get_num();
}
}
for (int i = 0; i <= n; i++) {
vis[i] = 0;
d[i] = 1e9;
}
d[0] = 0;
Q.push({0, 0});
int ans = 0;
while (!Q.empty()) {
re h = Q.top();
Q.pop();
if (vis[h.d]) continue;
vis[h.d] = 1;
ans += h.w;
for (int i = 0; i <= n; i++) {
if (d[i] > v[h.d][i]) {
d[i] = v[h.d][i];
Q.push({i, d[i]});
}
}
}
cout << ans;
return 0;
}

时间效率对比

从上至下依次为堆优化的Prim,Prim,Kruskal:
从上至下依次为堆优化的Prim,Prim,Kruskal