Posted on 2009-04-24 10:55
superman 阅读(105)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("agrinet.in", "r", stdin);
8 freopen("agrinet.out", "w", stdout);
9
10 int n, map[100][100];
11
12 cin >> n;
13 for (int i = 0; i < n; i++)
14 for (int j = 0; j < n; j++)
15 cin >> map[i][j];
16
17 //=====prim=====
18 int lowcost[100];
19 int vset[100];
20 int ans = 0;
21
22 vset[0] = 1;
23 for (int i = 1; i < n; i++)
24 {
25 lowcost[i] = map[0][i];
26 vset[i] = 0;
27 }
28
29 for (int k = 1; k < n; k++)
30 {
31 int min = INT_MAX, p;
32 for (int i = 0; i < n; i++)
33 if (vset[i] == 0 && lowcost[i] < min)
34 {
35 min = lowcost[i];
36 p = i;
37 }
38 ans += min;
39 vset[p] = 1;
40 for (int i = 0; i < n; i++)
41 if (vset[i] == 0 && map[p][i] < lowcost[i])
42 lowcost[i] = map[p][i];
43 }
44
45 cout << ans << endl;
46
47 return 0;
48 }
49