Posted on 2008-05-06 07:49
superman 阅读(556)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1203 C++ 00:00.01 924K */
2 #include <math.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int n;
8 double map[100][100];
9
10 double prim()
11 {
12 double lowcost[100], ans = 0.0;
13 bool vset[100] = { true };
14
15 for(int i = 1; i < n; i++)
16 lowcost[i] = map[0][i];
17
18 int v = 0;
19 for(int i = 1; i < n; i++)
20 {
21 double min = INT_MAX; int idx;
22 for(int j = 0; j < n; j++)
23 if(vset[j] == false && lowcost[j] < min)
24 {
25 min = lowcost[j];
26 idx = j;
27 }
28
29 ans += min;
30
31 vset[idx] = true;
32 v = idx;
33
34 for(int j = 0; j < n; j++)
35 if(vset[j] == false && map[v][j] < lowcost[j])
36 lowcost[j] = map[v][j];
37 }
38 return ans;
39 }
40
41 int main()
42 {
43 cout.setf(ios_base::showpoint);
44 cout.setf(ios_base::fixed);
45 cout.precision(2);
46
47 int C = 1;
48
49 cin >> n;
50
51 while(n)
52 {
53 double x[100], y[100];
54 for(int i = 0; i < n; i++)
55 cin >> x[i] >> y[i];
56
57 for(int i = 0; i < n - 1; i++)
58 for(int j = i + 1; j < n; j++)
59 map[i][j] = map[j][i] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
60
61 cout << "Case #" << C++ << ':' << endl;
62 cout << "The minimal distance is: " << prim() << endl;
63
64 cin >> n;
65 if(n)
66 cout << endl;
67 }
68
69 return 0;
70 }
71