首先POJ題目：
鏈接：1251 Jungle Roads
題目大意：純求最小生成樹，結果為最小權值邊的和。采用鄰接表
代碼：
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <queue>
5 using namespace std;
6
7 #define maxn 30 //最大頂點個數
8 int n; //頂點數，邊數
9
10 struct arcnode //邊結點
11 {
12 int vertex; //與表頭結點相鄰的頂點編號
13 int weight; //連接兩頂點的邊的權值
14 arcnode * next; //指向下一相鄰接點
15 arcnode() {}
16 arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
17 };
18
19 struct vernode //頂點結點，為每一條鄰接表的表頭結點
20 {
21 int vex; //當前定點編號
22 arcnode * firarc; //與該頂點相連的第一個頂點組成的邊
23 }Ver[maxn];
24
25 void Init() //建立圖的鄰接表需要先初始化，建立頂點結點
26 {
27 for(int i = 1; i <= n; i++)
28 {
29 Ver[i].vex = i;
30 Ver[i].firarc = NULL;
31 }
32 }
33
34 void Insert(int a, int b, int w) //頭插法，效率更高，但不能去重邊
35 {
36 arcnode * q = new arcnode(b, w);
37 if(Ver[a].firarc == NULL)
38 Ver[a].firarc = q;
39 else
40 {
41 arcnode * p = Ver[a].firarc;
42 q->next = p;
43 Ver[a].firarc = q;
44 }
45 }
46 struct node //保存key值的結點
47 {
48 int v;
49 int key;
50 friend bool operator<(node a, node b) //自定義優先級，key小的優先
51 {
52 return a.key > b.key;
53 }
54 };
55
56 #define INF 0xfffff //權值上限
57 int parent[maxn]; //每個結點的父節點
58 bool visited[maxn]; //是否已經加入樹種
59 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
60 priority_queue<node> q; //優先隊列stl實現
61 void Prim(int s) //s表示根結點
62 {
63 for(int i = 1; i <= n; i++) //初始化
64 {
65 vx[i].v = i;
66 vx[i].key = INF;
67 parent[i] = -1;
68 visited[i] = false;
69 }
70 vx[s].key = 0;
71 q.push(vx[s]);
72 while(!q.empty())
73 {
74 node nd = q.top(); //取隊首，記得趕緊pop掉
75 visited[nd.v] = true;
76 q.pop();
77 arcnode * p = Ver[nd.v].firarc;
78 while(p != NULL) //找到所有相鄰結點，若未訪問，則入隊列
79 {
80 if(!visited[p->vertex] && p->weight < vx[p->vertex].key)
81 {
82 parent[p->vertex] = nd.v;
83 vx[p->vertex].key = p->weight;
84 vx[p->vertex].v = p->vertex;
85 q.push(vx[p->vertex]);
86 }
87 p = p->next;
88 }
89 }
90 }
91 void Show() //打印圖的鄰接表（有權值）
92 {
93 for(int i = 1; i <= n; i++)
94 {
95 cout << Ver[i].vex;
96 arcnode * p = Ver[i].firarc;
97 while(p != NULL)
98 {
99 cout << "->(" << p->vertex << "," << p->weight << ")";
100 p = p->next;
101 }
102 cout << "->NULL" << endl;
103 }
104 }
105 int main()
106 {
107 int k, d;
108 char x, y;
109 while(cin >> n && n!=0)
110 {
111 Init();
112 for(int i = 1; i < n; i++)
113 {
114 cin >> x >> k;
115 while(k--)
116 {
117 cin >> y >> d;
118 Insert(x-'A'+1, y-'A'+1, d);
119 Insert(y-'A'+1, x-'A'+1, d);
120 }
121 }
122 Prim(1);
123 int ans = 0;
124 for(int i = 1; i <= n; i++)
125 ans += vx[i].key;
126 printf("%d\n", ans);
127 }
128 return 0;
129 }
鏈接：1258 Agri-Net
題目大意：求最小生成樹，鄰接矩陣實現
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 using namespace std;
5
6 #define maxn 110
7 #define INF 100020 //預定於的最大值
8 int n; //頂點數、邊數
9 int g[maxn][maxn]; //鄰接矩陣表示
10
11 struct node //保存key值的結點
12 {
13 int v;
14 int key;
15 friend bool operator<(node a, node b) //自定義優先級，key小的優先
16 {
17 return a.key > b.key;
18 }
19 };
20 int parent[maxn]; //每個結點的父節點
21 bool visited[maxn]; //是否已經加入樹種
22 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
23 priority_queue<node> q; //優先隊列stl實現
24 void Prim(int s) //s表示根結點
25 {
26 for(int i = 1; i <= n; i++) //初始化
27 {
28 vx[i].v = i;
29 vx[i].key = INF;
30 parent[i] = -1;
31 visited[i] = false;
32 }
33 vx[s].key = 0;
34 q.push(vx[s]);
35 while(!q.empty())
36 {
37 node nd = q.top(); //取隊首，記得趕緊pop掉
38 q.pop();
39 if(visited[nd.v] == true) //深意，因為push機器的可能是重復但是權值不同的點，我們只取最小的
40 continue;
41 int st = nd.v;
42 //cout << nd.v << " " << nd.key << endl;
43 visited[nd.v] = true;
44 for(int j = 1; j <= n; j++)
45 {
46 if(j!=st && !visited[j] && g[st][j] < vx[j].key) //判斷
47 {
48 parent[j] = st;
49 vx[j].key = g[st][j];
50 q.push(vx[j]);
51
52 }
53 }
54 }
55 }
56 int main()
57 {
58 while(~scanf("%d", &n))
59 {
60 for(int i = 1; i <= n; i++)
61 for(int j = 1; j <= n; j++)
62 {
63 scanf("%d", &g[i][j]);
64 if(g[i][j] == 0)
65 g[i][j] = INF;
66 }
67 Prim(1);
68 int ans = 0;
69 for(int i = 1; i <= n; i++)
70 ans += vx[i].key;
71 printf("%d\n", ans);
72
73 }
74 return 0;
75 }
鏈接：1789 Truck History
題目大意：n種卡車，互相之間的差別為同一位置上不同字母的個數，這相當於每個點的權值，根據這個權值來求最小生成樹。
代碼，采用鄰接矩陣：
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 using namespace std;
5
6 #define maxn 2020
7 #define INF 10 //預定於的最大值
8 int n; //頂點數、邊數
9 int g[maxn][maxn]; //鄰接矩陣表示
10
11 struct node //保存key值的結點
12 {
13 int v;
14 int key;
15 friend bool operator<(node a, node b) //自定義優先級，key小的優先
16 {
17 return a.key > b.key;
18 }
19 };
20 bool visited[maxn]; //是否已經加入樹種
21 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
22 priority_queue<node> q; //優先隊列stl實現
23 void Prim(int s) //s表示根結點
24 {
25 for(int i = 1; i <= n; i++) //初始化
26 {
27 vx[i].v = i;
28 vx[i].key = INF;
29 visited[i] = false;
30 }
31 vx[s].key = 0;
32 q.push(vx[s]);
33 while(!q.empty())
34 {
35 node nd = q.top(); //取隊首，記得趕緊pop掉
36 q.pop();
37 if(visited[nd.v] == true) //深意，因為push機器的可能是重復但是權值不同的點，我們只取最小的
38 continue;
39 int st = nd.v;
40 visited[nd.v] = true;
41 for(int j = 1; j <= n; j++)
42 {
43 if(j!=st && !visited[j] && g[st][j] < vx[j].key) //判斷
44 {
45 vx[j].key = g[st][j];
46 q.push(vx[j]);
47 }
48 }
49 }
50 }
51 char tk[2020][8];
52 int main()
53 {
54 while(scanf("%d", &n), n)
55 {
56 for(int i = 1; i <= n; i++)
57 scanf("%s", tk[i]);
58 for(int i = 1; i < n; i++)
59 {
60 for(int j = i+1; j <= n; j++)
61 {
62 int cnt = 0;
63 for(int k = 0; k < 7; k++)
64 if(tk[i][k] != tk[j][k])
65 cnt++;
66 g[i][j] = g[j][i] = cnt;
67 }
68 }
69 Prim(1);
70 int ans = 0;
71 for(int i = 1; i <= n; i++)
72 ans += vx[i].key;
73 printf("The highest possible quality is 1/%d.\n", ans);
74 }
75 return 0;
76 }
鏈接：2485 Highways
題目大意：依然是最小生成樹，輸出權值最大的邊。
代碼：
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 using namespace std;
5
6 #define maxn 510
7 #define INF 0xffffff //預定於的最大值
8 int n; //頂點數、邊數
9 int g[maxn][maxn]; //鄰接矩陣表示
10
11 struct node //保存key值的結點
12 {
13 int v;
14 int key;
15 friend bool operator<(node a, node b) //自定義優先級，key小的優先
16 {
17 return a.key > b.key;
18 }
19 };
20 bool visited[maxn]; //是否已經加入樹中
21 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
22 priority_queue<node> q; //優先隊列stl實現
23 void Prim(int s) //s表示根結點
24 {
25 for(int i = 1; i <= n; i++) //初始化
26 {
27 vx[i].v = i;
28 vx[i].key = INF;
29 visited[i] = false;
30 }
31 vx[s].key = 0;
32 q.push(vx[s]);
33 while(!q.empty())
34 {
35 node nd = q.top(); //取隊首，記得趕緊pop掉
36 q.pop();
37 if(visited[nd.v] == true) //深意，因為push機器的可能是重復但是權值不同的點，我們只取最小的
38 continue;
39 int st = nd.v;
40 visited[nd.v] = true;
41 for(int j = 1; j <= n; j++)
42 {
43 if(j!=st && !visited[j] && g[st][j] < vx[j].key) //判斷
44 {
45 vx[j].key = g[st][j];
46 q.push(vx[j]);
47 }
48 }
49 }
50 }
51 int main()
52 {
53 int t;
54 scanf("%d", &t);
55 while(t--)
56 {
57 scanf("%d", &n);
58 for(int i = 1; i <= n; i++)
59 {
60 for(int j = 1; j <= n; j++)
61 scanf("%d", &g[i][j]);
62 g[i][i] = INF;
63 }
64 Prim(1);
65 int ans = 0;
66 for(int i = 1; i <= n; i++)
67 if(vx[i].key > ans)
68 ans = vx[i].key;
69 printf("%d\n", ans);
70
71 }
72 return 0;
73 }
HDOJ
鏈接：1863 暢通工程
題目大意：求全省暢通最低成本，最小生成樹，判斷能否生成一棵樹，如果能輸出最小代價，不能輸出 ？
代碼，采用鄰接表：
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 using namespace std;
5
6 #define maxn 110 //最大頂點個數
7 int n, m; //頂點數，邊數
8
9 struct arcnode //邊結點
10 {
11 int vertex; //與表頭結點相鄰的頂點編號
12 int weight; //連接兩頂點的邊的權值
13 arcnode * next; //指向下一相鄰接點
14 arcnode() {}
15 arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
16 };
17
18 struct vernode //頂點結點，為每一條鄰接表的表頭結點
19 {
20 int vex; //當前定點編號
21 arcnode * firarc; //與該頂點相連的第一個頂點組成的邊
22 }Ver[maxn];
23
24 void Init() //建立圖的鄰接表需要先初始化，建立頂點結點
25 {
26 for(int i = 1; i <= n; i++)
27 {
28 Ver[i].vex = i;
29 Ver[i].firarc = NULL;
30 }
31 }
32
33 void Insert(int a, int b, int w) //頭插法，效率更高，但不能去重邊
34 {
35 arcnode * q = new arcnode(b, w);
36 if(Ver[a].firarc == NULL)
37 Ver[a].firarc = q;
38 else
39 {
40 arcnode * p = Ver[a].firarc;
41 q->next = p;
42 Ver[a].firarc = q;
43 }
44 }
45
46 struct node //保存key值的結點
47 {
48 int v;
49 int key;
50 friend bool operator<(node a, node b) //自定義優先級，key小的優先
51 {
52 return a.key > b.key;
53 }
54 };
55
56 #define INF 999999999 //權值上限
57 int parent[maxn]; //每個結點的父節點
58 bool visited[maxn]; //是否已經加入樹種
59 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
60 priority_queue<node> q; //優先隊列stl實現
61 void Prim(int s) //s表示根結點
62 {
63 for(int i = 1; i <= n; i++) //初始化
64 {
65 vx[i].v = i;
66 vx[i].key = INF;
67 parent[i] = -1;
68 visited[i] = false;
69 }
70 vx[s].key = 0;
71 q.push(vx[s]);
72 while(!q.empty())
73 {
74 node nd = q.top(); //取隊首，記得趕緊pop掉
75 q.pop();
76 if(visited[nd.v] == true)
77 continue;
78 visited[nd.v] = true;
79 arcnode * p = Ver[nd.v].firarc;
80 while(p != NULL) //找到所有相鄰結點，若未訪問，則入隊列
81 {
82 if(!visited[p->vertex] && p->weight < vx[p->vertex].key)
83 {
84 parent[p->vertex] = nd.v;
85 vx[p->vertex].key = p->weight;
86 vx[p->vertex].v = p->vertex;
87 q.push(vx[p->vertex]);
88 }
89 p = p->next;
90 }
91 }
92 }
93 int main()
94 {
95 int a, b, w;
96 while(scanf("%d%d", &m, &n), m)
97 {
98 Init();
99 while(m--)
100 {
101 scanf("%d%d%d", &a, &b, &w);
102 if(a != b)
103 {
104 Insert(a, b, w);
105 Insert(b, a, w);
106 }
107 }
108 Prim(1);
109 int cnt = 0, ans = 0;
110 for(int i = 1; i <= n; i++)
111 {
112 if(parent[i] == -1)
113 cnt++;
114 ans += vx[i].key;
115 }
116 if(cnt >= 2)
117 printf("?\n");
118 else
119 printf("%d\n", ans);
120
121 }
122 return 0;
123 }
鏈接：1875 暢通工程再續
題目大意：依然是最小生成樹，但是點換成了坐標表示，權值表示為兩點的距離，求最小權值的和。
代碼，鄰接表：
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <queue>
5 using namespace std;
6
7 #define maxn 110 //最大頂點個數
8 int n; //頂點數，邊數
9
10 struct arcnode //邊結點
11 {
12 int vertex; //與表頭結點相鄰的頂點編號
13 double weight; //連接兩頂點的邊的權值
14 arcnode * next; //指向下一相鄰接點
15 arcnode() {}
16 arcnode(int v,double w):vertex(v),weight(w),next(NULL) {}
17 };
18
19 struct vernode //頂點結點，為每一條鄰接表的表頭結點
20 {
21 int vex; //當前定點編號
22 arcnode * firarc; //與該頂點相連的第一個頂點組成的邊
23 }Ver[maxn];
24
25 void Init() //建立圖的鄰接表需要先初始化，建立頂點結點
26 {
27 for(int i = 1; i <= n; i++)
28 {
29 Ver[i].vex = i;
30 Ver[i].firarc = NULL;
31 }
32 }
33
34 void Insert(int a, int b, double w) //尾插法，插入以a為起點，b為終點，權為w的邊，效率不如頭插，但是可以去重邊
35 {
36 arcnode * q = new arcnode(b, w);
37 if(Ver[a].firarc == NULL)
38 Ver[a].firarc = q;
39 else
40 {
41 arcnode * p = Ver[a].firarc;
42 q->next = p;
43 Ver[a].firarc = q;
44 }
45 }
46
47 struct node //保存key值的結點
48 {
49 int v;
50 double key;
51 friend bool operator<(node a, node b) //自定義優先級，key小的優先
52 {
53 return a.key > b.key;
54 }
55 };
56
57 #define INF 1e10 //權值上限
58 #define eps 1e-9
59 int parent[maxn]; //每個結點的父節點
60 bool visited[maxn]; //是否已經加入樹種
61 node vx[maxn]; //保存每個結點與其父節點連接邊的權值
62 priority_queue<node> q; //優先隊列stl實現
63 void Prim(int s) //s表示根結點
64 {
65 for(int i = 1; i <= n; i++) //初始化
66 {
67 vx[i].v = i;
68 vx[i].key = INF;
69 parent[i] = -1;
70 visited[i] = false;
71 }
72 vx[s].key = 0;
73 q.push(vx[s]);
74 while(!q.empty())
75 {
76 node nd = q.top(); //取隊首，記得趕緊pop掉
77 q.pop();
78 if(visited[nd.v] == true)
79 continue;
80 visited[nd.v] = true;
81 arcnode * p = Ver[nd.v].firarc;
82 while(p != NULL) //找到所有相鄰結點，若未訪問，則入隊列
83 {
84 if(!visited[p->vertex] && p->weight < vx[p->vertex].key)
85 {
86 parent[p->vertex] = nd.v;
87 vx[p->vertex].key = p->weight;
88 vx[p->vertex].v = p->vertex;
89 q.push(vx[p->vertex]);
90 }
91 p = p->next;
92 }
93 }
94 }
95 void Show() //打印圖的鄰接表（有權值）
96 {
97 for(int i = 1; i <= n; i++)
98 {
99 cout << Ver[i].vex;
100 arcnode * p = Ver[i].firarc;
101 while(p != NULL)
102 {
103 cout << "->(" << p->vertex << "," << p->weight << ")";
104 p = p->next;
105 }
106 cout << "->NULL" << endl;
107 }
108 }
109 struct Point
110 {
111 int x, y;
112 }PT[maxn];
113 double dis(Point p1, Point p2)
114 {
115 return 100.0*sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
116 }
117 int main()
118 {
119 int t;
120 scanf("%d", &t);
121 while(t--)
122 {
123 scanf("%d", &n);
124 for(int i = 1; i <= n; i++)
125 scanf("%d%d", &PT[i].x, &PT[i].y);
126 Init();
127 for(int i = 1; i < n; i++)
128 for(int j = i+1; j <= n; j++)
129 {
130 double d = dis(PT[i], PT[j]);
131 if(1000.00 - d > eps || d -100000.00 > eps)
132 continue;
133 Insert(i, j, d);
134 Insert(j, i, d);
135 }
136 Prim(1);
137 int cnt = 0;
138 double ans = 0;
139 for(int i = 1; i <= n; i++)
140 {
141 if(parent[i] == -1)
142 cnt++;
143 ans += vx[i].key;
144 if(cnt == 2)
145 break;
146 }
147 if(cnt == 2)
148 printf("oh!\n");
149 else
150 printf("%.1lf\n", ans);
151 }
152 return 0;
153 }
鏈接：1879
題目大意：這道題問題在於其中有些邊已經存在，即有些路已經被修建好了，我們只需要將已經建好的邊的權值置為0就必定會加入到最小生成樹中
問題：這道題用Prim暫時還沒過，應該是有什麼坑數據，還在鑽研
下面貼Kruskal的代碼：
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5
6 #define maxn 110
7 struct eage
8 {
9 int u, v, w;
10 }EG[5050];
11 int parent[maxn];
12 int n, m;
13 bool cmp(eage a, eage b)
14 {
15 return a.w < b.w;
16 }
17 int Find(int x)
18 {
19 if(parent[x] == -1) return x;
20 return Find(parent[x]);
21 }
22 void Kruskal()
23 {
24 for(int i = 1; i <= n; i++)
25 parent[i] = -1;
26 sort(EG+1, EG+m+1, cmp);
27 int ans = 0;
28 for(int i = 1; i <= m; i++)
29 {
30 int x = Find(EG[i].u);
31 int y = Find(EG[i].v);
32 if(x != y)
33 {
34 ans += EG[i].w;
35 parent[x] = y;
36 }
37 }
38 printf("%d\n", ans);
39 }
40 int main()
41 {
42 int w, f;
43 while(scanf("%d", &n), n)
44 {
45 m = n*(n-1)/2;
46 for(int i = 1; i <= m; i++)
47 {
48 scanf("%d%d%d%d", &EG[i].u, &EG[i].v, &w, &f);
49 if(f == 1)
50 w = 0;
51 EG[i].w = w;
52 }
53 Kruskal();
54 }
55 return 0;
56 }
