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