题目分析：
其实就是求图的最小生成树。有两种方法。prim法和kruskal法。prim法只与节点有关，与边无关，所以适合于求边稠密的网的最小生成树。而kruskal算法与边有关，故其适合于求边比较稀疏的网络。
prim算法：
1）初始化set集为随意的一个节点，这里初始化为1。
2）找出与set集中的点相连的，花费最小的并且不再set集中的点，加入set集中。为了计算的方便，先将每个节点相连的所有边按权值升序排列。
3）直到所有的点都加到set集中，算法就停止了。
kruskal算法：
1）每次找权值最小的边，如果节点没有访问过，就加到set集中。如果访问过了，就合并两个set集。
2）这里为了剪去不必要的迭代，如果连通区域为1，并且所有的点都已经访问过了，就退出。
参考代码：
prim算法的代码：
[cpp]
#include
#include
#include
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
#include
#include
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