csp 201412_4 最优灌溉

摘要:

最小生成树 prim算法

问题描述

  雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉。
  为了灌溉,雷雷需要建立一些水渠,以连接水井和麦田,雷雷也可以利用部分麦田作为“中转站”,利用水渠连接不同的麦田,这样只要一片麦田能被灌溉,则与其连接的麦田也能被灌溉。
  现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用(注意不是所有麦田之间都可以建立水渠)。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

  输入的第一行包含两个正整数n, m,分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。
  接下来m行,每行包含三个整数ai, bi, ci,表示第ai片麦田与第bi片麦田之间可以建立一条水渠,所需要的费用为ci。

输出格式

  输出一行,包含一个整数,表示灌溉所有麦田所需要的最小费用。

样例输入

4 4
1 2 1
2 3 4
2 4 2
3 4 3

样例输出

6

样例说明

  建立以下三条水渠:麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

###评测用例规模与约定

  前20%的评测用例满足:n≤5。
  前40%的评测用例满足:n≤20。
  前60%的评测用例满足:n≤100。
  所有评测用例都满足:1≤n≤1000,1≤m≤100,000,1≤ci≤10,000。

思路

不得不说早年的csp考试题目果然很直接。。这道题直接套用prim算法的模板就行甚至都不需要小trick。在这里顺便把prim算法重新说下吧,prim算法主要用来构建最小生成树,算法的主要思想是,所有的点构成点集V,已经被我们访问的点构成点集S,所以点集V就被分为了点集S和点集V-S。我们每次都要从点集V-S中寻找一个距离点集S最近的点加入到点集S中,这个最近的距离所对应的那条边就被加入到最小生成树中。实现的时候,我们需要一个数组d[],他记录的是各个节点到集合S的距离,这道题我是使用邻接矩阵来实现的。一些坑和需要注意的点会在代码注释里面写出来。

AC代码

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
#include <iostream>
#include <algorithm>
#define MAXN 1010
#define INF 1000000

using namespace std;

int G[MAXN][MAXN];
int d[MAXN]; //借调到集合S的最短距离
bool vis[MAXN] = {false}; // 记录是否被访问

int prim(int n){ //默认以第一个节点作为起点
int ans = 0;
fill(d, d+MAXN, INF); //注意:fill的第一个和第二个参数应该是指针,所以不要写成了d[0]
d[0] = 0;
for(int i=0; i<n; i++){
int min_n = -1, min = INF;
for(int j=0; j<n; j++){
if(vis[j] == false && d[j] < min){
min = d[j];
min_n = j;
}
}
if(min_n == -1){ //注意:这个判断在这道题中似乎是不需要的,但是规范的prim算法应该需要这个判断,当给出的图不是一个连通分量的时候应该返回-1
return -1;
}
ans += min;
vis[min_n] = true;
for(int j=0; j<MAXN; j++){
if(G[min_n][j] < d[j] && vis[j] == false){
d[j] = G[min_n][j];
}
}
}
return ans;
}

int main(){
int n, m, a, b, c;
cin >> n >> m;
fill(G[0], G[0]+MAXN*MAXN, INF);
for(int i=0; i<m; i++){
cin >> a >> b >> c;
//注意:题目给出的节点的序号是从1开始的,而我们的数组是从0开始,所以需要减一
//注意:给G[a-1][b-1]赋值后不要忘记给G[b-1][a-1]赋值,我一开始就忘了=_=
G[a-1][b-1] = c;
G[b-1][a-1] = c;
}
cout << prim(n);
return 0;
}