题目链接
1 /*
2 Name:hdu-1102-Constructing Roads
3 Copyright:
4 Author:
5 Date: 2018/4/18 9:35:08
6 Description:
7 prime算法模板
8 */
9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <utility>
13 #include <vector>
14 using namespace std;
15 const int MAXN = 110, INF = 0x3f3f3f3f;
16 bool v[MAXN];
17 int N;
18 int dis[MAXN];
19 vector<pair<int ,int>> g[MAXN];
20 int Prim() {
21 memset(v ,0 , sizeof(v)) ;
22 for (int i=0; i<=N; i++) dis[i] = INF;
23 dis[1] = 0;
24 int ans = 0;
25 for (int i=0; i<N; i++) {
26 int mark = -1;
27 for (int j=0; j<N; j++) {
28 if (!v[j]) {
29 if (mark == -1) mark = j;
30 else if (dis[j]<dis[mark]) mark = j;
31 }
32 }
33 if (mark == -1) break;
34 v[mark] = 1;
35 ans += dis[mark] ;
36 for (int j=0; j<g[mark].size(); ++j) {
37 if (!v[g[mark][j].first]) {
38 int x =g[mark][j].first;
39 dis[x] = min(dis[x], g[mark][j].second);
40 }
41 }
42 }
43 return ans;
44 }
45
46 int main()
47 {
48 // freopen("in.txt", "r", stdin);
49
50 while (~scanf("%d", &N)) {
51 for (int i=0; i<109; i++) {//clear
52 while (!g[i].empty()) g[i].pop_back();
53 }
54 for (int i=0; i<N; i++) {
55 for (int j=0; j<N; j++) {
56 int tmp;
57 scanf("%d", &tmp);
58 g[i].push_back(make_pair(j, tmp));
59 }
60 }
61 int q;
62 cin>>q;
63 for (int i=1; i<=q; i++) {
64 int a, b;
65 scanf("%d %d", &a, &b);
66 a--,b--;
67 g[a][b].second = g[b][a].second = 0;
68 }
69 cout<<Prim()<<endl;
70 }
71 return 0;
72 }