題目分析：
其實就是求圖的最小生成樹。有兩種方法。prim法和kruskal法。prim法只與節點有關，與邊無關，所以適合於求邊稠密的網的最小生成樹。而kruskal算法與邊有關，故其適合於求邊比較稀疏的網絡。
prim算法：
1）初始化set集為隨意的一個節點，這裡初始化為1。
2）找出與set集中的點相連的，花費最小的並且不再set集中的點，加入set集中。為了計算的方便，先將每個節點相連的所有邊按權值升序排列。
3）直到所有的點都加到set集中，算法就停止了。
kruskal算法：
1）每次找權值最小的邊，如果節點沒有訪問過，就加到set集中。如果訪問過了，就合並兩個set集。
2）這裡為了剪去不必要的迭代，如果連通區域為1，並且所有的點都已經訪問過了，就退出。
參考代碼：
prim算法的代碼：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct NODE
{
int to;
int w;
};
NODE Map[501][501];//Map[i][0].to存放節點i相鄰的點的個數
bool used[501];
int set[501];
int compare(const void *a, const void *b)
{
NODE *p1 = (NODE *)a;
NODE *p2 = (NODE *)b;
return p1->w - p2->w;
}
void GetMap(int n)
{
for(int i = 1; i <= n; ++i)
qsort(&Map[i][1], Map[i][0].to, sizeof(Map[i][0]), compare);
}
int Prim(int n)
{
int num = 1;//set集合內點的個數
int i,j;
int ans = 0;
NODE temp;
set[0] = 1;
used[1] = true;
while(num < n)
{
temp.to = -1;
temp.w = 101;
for(i = 0; i < num; ++i)
{
for(j = 1; j <= Map[set[i]][0].to; ++j)
{
if(!used[Map[set[i]][j].to])
{
if(Map[set[i]][j].w < temp.w)
temp = Map[set[i]][j];
break;
}
}//end for j
}//end for i
if(temp.to != -1)
{
ans += temp.w;
set[num++] = temp.to;
used[temp.to] = true;
}
}//end for while
return ans;
}
int main()
{
int t,i;
int v,e;
int a,b,c;
int ans;
scanf("%d", &t);
while(t--)
{
memset(used,0,sizeof(used));
scanf("%d %d", &v, &e);
for(i = 0; i <= v; ++i)
Map[i][0].to = 0;
for(i = 0; i < e; ++i)
{
scanf("%d %d %d", &a, &b, &c);
++(Map[a][0].to);
++(Map[b][0].to);
Map[a][Map[a][0].to].to = b;
Map[a][Map[a][0].to].w = c;
Map[b][Map[b][0].to].to = a;
Map[b][Map[b][0].to].w = c;
}
scanf("%d", &b);
for(i = 1; i < v; ++i)
{
scanf("%d", &a);
b = b < a ? b : a;
}
GetMap(v);
ans = Prim(v);
ans += b;
printf("%d\n", ans);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct NODE
{
int to;
int w;
};
NODE Map[501][501];//Map[i][0].to存放節點i相鄰的點的個數
bool used[501];
int set[501];
int compare(const void *a, const void *b)
{
NODE *p1 = (NODE *)a;
NODE *p2 = (NODE *)b;
return p1->w - p2->w;
}
void GetMap(int n)
{
for(int i = 1; i <= n; ++i)
qsort(&Map[i][1], Map[i][0].to, sizeof(Map[i][0]), compare);
}
int Prim(int n)
{
int num = 1;//set集合內點的個數
int i,j;
int ans = 0;
NODE temp;
set[0] = 1;
used[1] = true;
while(num < n)
{
temp.to = -1;
temp.w = 101;
for(i = 0; i < num; ++i)
{
for(j = 1; j <= Map[set[i]][0].to; ++j)
{
if(!used[Map[set[i]][j].to])
{
if(Map[set[i]][j].w < temp.w)
temp = Map[set[i]][j];
break;
}
}//end for j
}//end for i
if(temp.to != -1)
{
ans += temp.w;
set[num++] = temp.to;
used[temp.to] = true;
}
}//end for while
return ans;
}
int main()
{
int t,i;
int v,e;
int a,b,c;
int ans;
scanf("%d", &t);
while(t--)
{
memset(used,0,sizeof(used));
scanf("%d %d", &v, &e);
for(i = 0; i <= v; ++i)
Map[i][0].to = 0;
for(i = 0; i < e; ++i)
{
scanf("%d %d %d", &a, &b, &c);
++(Map[a][0].to);
++(Map[b][0].to);
Map[a][Map[a][0].to].to = b;
Map[a][Map[a][0].to].w = c;
Map[b][Map[b][0].to].to = a;
Map[b][Map[b][0].to].w = c;
}
scanf("%d", &b);
for(i = 1; i < v; ++i)
{
scanf("%d", &a);
b = b < a ? b : a;
}
GetMap(v);
ans = Prim(v);
ans += b;
printf("%d\n", ans);
}
return 0;
}kruskal算法的代碼：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct EDGE
{
int from;
int to;
int w;
};
EDGE edge[124760];//所有的邊
bool used[501];
int set[501];
int compare(const void *a, const void *b)
{
EDGE *p1 = (EDGE *)a;
EDGE *p2 = (EDGE *)b;
return p1->w - p2->w;
}
int find(int k)
{
int r = set[k];
while(r != set[r])
r = set[r];
return r;
}
void Merge(int r1, int r2)
{
if(r1 < r2)
set[r2] = r1;
else
set[r1] = r2;
}
int Kruskal(int v, int e)
{
int ans = 0;
int t, num;//t為連通區域的個數，num為已訪問的節點的個數
int r1, r2;
t = num = 0;
while(num != v && t != 1)
{
for(int i = 0; i < e; ++i)
{
if(!used[edge[i].from])
{
++t;
++num;
used[edge[i].from] = true;
}
if(!used[edge[i].to])
{
++t;
++num;
used[edge[i].to] = true;
}
r1 = find(edge[i].from);
r2 = find(edge[i].to);
if(r1 != r2)
{
--t;
Merge(r1, r2);
ans += edge[i].w;
}
}//end for i
}//end while
return ans;
}
int main()
{
int t,i;
int v,e;
int a,b,c;
int ans;
scanf("%d", &t);
while(t--)
{
memset(used,0,sizeof(used));
scanf("%d %d", &v, &e);
for(i = 1; i <= v; ++i)
set[i] = i;
for(i = 0; i < e; ++i)
{
scanf("%d %d %d", &a, &b, &c);
edge[i].from = a;
edge[i].to = b;
edge[i].w = c;
}
qsort(edge, e, sizeof(edge[0]), compare);
scanf("%d", &b);
for(i = 1; i < v; ++i)
{
scanf("%d", &a);
b = b < a ? b : a;
}
ans = Kruskal(v, e);
ans += b;
printf("%d\n", ans);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct EDGE
{
int from;
int to;
int w;
};
EDGE edge[124760];//所有的邊
bool used[501];
int set[501];
int compare(const void *a, const void *b)
{
EDGE *p1 = (EDGE *)a;
EDGE *p2 = (EDGE *)b;
return p1->w - p2->w;
}
int find(int k)
{
int r = set[k];
while(r != set[r])
r = set[r];
return r;
}
void Merge(int r1, int r2)
{
if(r1 < r2)
set[r2] = r1;
else
set[r1] = r2;
}
int Kruskal(int v, int e)
{
int ans = 0;
int t, num;//t為連通區域的個數，num為已訪問的節點的個數
int r1, r2;
t = num = 0;
while(num != v && t != 1)
{
for(int i = 0; i < e; ++i)
{
if(!used[edge[i].from])
{
++t;
++num;
used[edge[i].from] = true;
}
if(!used[edge[i].to])
{
++t;
++num;
used[edge[i].to] = true;
}
r1 = find(edge[i].from);
r2 = find(edge[i].to);
if(r1 != r2)
{
--t;
Merge(r1, r2);
ans += edge[i].w;
}
}//end for i
}//end while
return ans;
}
int main()
{
int t,i;
int v,e;
int a,b,c;
int ans;
scanf("%d", &t);
while(t--)
{
memset(used,0,sizeof(used));
scanf("%d %d", &v, &e);
for(i = 1; i <= v; ++i)
set[i] = i;
for(i = 0; i < e; ++i)
{
scanf("%d %d %d", &a, &b, &c);
edge[i].from = a;
edge[i].to = b;
edge[i].w = c;
}
qsort(edge, e, sizeof(edge[0]), compare);
scanf("%d", &b);
for(i = 1; i < v; ++i)
{
scanf("%d", &a);
b = b < a ? b : a;
}
ans = Kruskal(v, e);
ans += b;
printf("%d\n", ans);
}
return 0;
}
由於prim方法針對節點，而kruskal方法針對邊，所以二者的數據結構有點不一樣。
