whyisyoung's Blog

If you can not persist, you will never succeed :)

EOJ 2067 Solution Report - Building Roads

| Comments

原题地址:EOJ 2067

keyword: 最小生成树(Minimum Spanning Tree), Prim Algorithm

1. 题目描述

标记为 1-N 的 N 个农场,它们分布在平面直角坐标系的第一象限,位置用 ($X_i$, $Y_i$ ) 标记。现已修好了 M 条路(每条路连接两个农场),请求出为了将所有的农场连接起来最少还需要修多长的路。

Note:

$ 1 \leqslant N \leqslant 1000$

$ 1 \leqslant M \leqslant 1000$

$ 1 \leqslant X_i \leqslant 1,000,000$

$ 1 \leqslant Y_i \leqslant 1,000,000$

2. 解题思路

熟悉图论的可能会立即想到数据结构书中对于最小生成树的描述:

在 n 个城市间最多可建造 $\frac{n(n-1)}{2}$ 条线路。如何在这些可能的线路中,选择其中 (n-1)条线路,使其总的代价最小,或者线路的总长度最短? 为了回答上述问题,引进最小(代价)生成树的概念。 一个带权连通无向图 G 的最小(代价)生成树是 G 的所有生成树中边上的权之和最小的一棵生成树。

本题其实就是求已知其中的几条边的情况下的最小生成树。

实现起来有两种差不多的方法.

思路1 :

对于已经修好的路

cost[i][j] = cost[j][i] = -1

其中 cost[i][j] 二维数组是代价邻接矩阵,也就是 i 和 j 之间的距离。

本题情况下,除了修好的路,默认有:

i = j , cost[i][j] = 0, 其余的就是正常的两点间距离。

对于 Prim 算法,

lowcost[i] 代表的是为了将某个顶点 i 加入到当前已生成的最小生成树中所需的最小代价, 所以对于已修好的路所涉及的两个顶点,他们的 lowcost 均为 -1, 是一定会被加入到最小生成树中的,但是再算最后的距离和的时候,这种 -1 是不应该被算进去的。

其余的部分基本就是按照书上的prim算法来,先找到与 i 最近的那个顶点 k,

然后将顶点 k 加入到最小生成树中,而由于 k 的加入,所以要改变剩下的点的最小代价。

思路2 :

对于已经修好的路

cost[i][j] = cost[j][i] = 0

由于与原有的 cost[i][i] = 0 可能冲突,故用一个 bool 数组 visit 表示所有点的访问情况,访问过的即代表已经被加入到 最小生成树中,这时候为了求距离和就不用再判断是否不为 -1 了, 直接加上 min 即可。(加 0 等于没加)

注意事项:

  1. 此题处理距离时要用 double,另外两点间最大距离 MAXDIS 也应设为 double, 更不要把 double 和 int 比较大小,如在找与 i 最近的那个顶点 k 时,设置的 min = MAXDIS, 这里的 min 就应该用 double。

  2. double 的输入输出

g++ 输出 double 用的是 "%.f" c++ 输出 double 用的是 "%.lf" 但是对于输入都是 "%lf"

代码如下:

version 1:

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
//
//  main.cpp
//  eoj2067
//
//  Created by whyisyoung on 3/15/14.
//  Copyright (c) 2014 whyisyoung. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1002;
const double MAXDIS = 10000000; // 这里写成 int 真是 WTF!!!

double X[maxn], Y[maxn];

double cost[maxn][maxn];
double lowcost[maxn];
double ans = 0;

void get_all_cost(double X[], double Y[], int N)
{
	for(int i = 1; i <= N; ++i) {
		for(int j = 1; j <= N; ++j) {
			if(i == j)
				cost[i][j] = 0;
			else
				cost[i][j] = sqrt((double)(X[i]-X[j])*(X[i]-X[j])+(double)(Y[i]-Y[j])*(Y[i]-Y[j]));
		}
	}
}

double prim(int N)
{
	ans = 0;

    for(int i = 1; i <= N; ++i) {
		lowcost[i] = cost[1][i];
	}

	int k = 0;

	for(int i = 1; i < N; ++i) {
		double min = MAXDIS; // 这里写成 int 真是 	WTF!!!
		for(int j = 1; j <= N; ++j) {
			if(lowcost[j] != 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;
			}
		}
		if(min == MAXDIS) // 找不到新的点可以加入到树中
			break;

		if(min != -1)
			ans += min;

        lowcost[k] = 0; // 将顶点 k 加入到最小生成树中

		for(int j = 1; j <= N; ++j) {
			if(lowcost[j] != 0 && cost[k][j] < lowcost[j]) {
				lowcost[j] = cost[k][j];
			}
		}
	}

	return ans;
}


int main()
{
	int N, M;
	int x, y;
	while(scanf("%d%d", &N, &M) != EOF) {
		for(int i = 1; i <= N; ++i) {
			scanf("%lf%lf", &X[i], &Y[i]);
		}

		get_all_cost(X, Y, N);

		for(int i = 0; i < M; ++i) {
			scanf("%d%d", &x, &y);
			cost[x][y] = -1;
			cost[y][x] = -1;
		}

		ans = prim(N);

		printf("%.2lf\n", ans);

	}

	return 0;
}

version 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
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
//
//  main.cpp
//  eoj2067
//
//  Created by whyisyoung on 3/15/14.
//  Copyright (c) 2014 whyisyoung. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 1002;
const double MAXDIS = 10000000;

double X[maxn], Y[maxn];
bool visit[maxn]; //记录某点是否访问过,即是否已加入到最小生成树中

double cost[maxn][maxn];
double lowcost[maxn];
double ans = 0;

void get_all_cost(double X[], double Y[], int N)
{
	for(int i = 1; i <= N; ++i) {
		for(int j = 1; j <= N; ++j) {
			if(i == j)
				cost[i][j] = 0;
			else
				cost[i][j] = sqrt((double)(X[i]-X[j])*(X[i]-X[j])+(double)(Y[i]-Y[j])*(Y[i]-Y[j]));
		}
	}
}

double prim(int N)
{
	ans = 0;

    for(int i = 1; i <= N; ++i) {
		lowcost[i] = cost[1][i];
	}
	visit[1] = 1;

	int k = 0;

	for(int i = 1; i < N; ++i) {
		double min = MAXDIS;
		for(int j = 1; j <= N; ++j) {
			if(!visit[j] && lowcost[j] < min) {
				min = lowcost[j];
				k = j;
			}
		}
		if(min == MAXDIS) // 找不到新的点可以加入到树中
			break;

		visit[k] = 1; // k 已被访问过
		ans += min;

		for(int j = 1; j <= N; ++j) {
			if(!visit[j] && cost[k][j] < lowcost[j]) {
				lowcost[j] = cost[k][j];
			}
		}
	}

	return ans;
}


int main()
{
	int N, M;
	int x, y;
	while(scanf("%d%d", &N, &M) != EOF) {

		memset(visit, 0, sizeof(visit));

		for(int i = 1; i <= N; ++i) {
			scanf("%lf%lf", &X[i], &Y[i]);
		}

		get_all_cost(X, Y, N);

		for(int i = 0; i < M; ++i) {
			scanf("%d%d", &x, &y);
			cost[x][y] = 0;
			cost[y][x] = 0;
		}

		ans = prim(N);

		printf("%.2lf\n", ans);
	}

	return 0;
}

Comments