思路
建立超级源点，添加所有点与源点的边，边权为该点的挖井费用，然后基本的最小生成树。
AC code
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int g[N][N];
int dist[N];
bool st[N];
int n;
int prim(){
memset(dist, 0x3f, sizeof(dist));
int res = 0;
for(int i = 0; i <= n; i++){
int t = -1;
for(int j = 0; j <= n; j++){
if(!st[j] && (t == -1 || dist[j] < dist[t])){
t = j;
}
}
st[t] = true;
if(i) res += dist[t];
for(int j = 0; j <= n; j++){
dist[j] = min(dist[j], g[t][j]);
}
}
return res;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
int w;
cin >> w;
g[0][i] = g[i][0] = w;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> g[i][j];
}
}
cout << prim() << endl;
return 0;
}
|
