本文共 1282 字，大约阅读时间需要 4 分钟。
标签：最小生成树
/* 题意：输出最小生成树的权值和。每组数据给出节点个数n，以下n-1行， 开头为起始节点，及与它相连的节点数目m，随后m组数据表示和它相连的节点以及边权值(用c++处理空格和换行符)。 思路：Kruskal。*/#include#include #include using namespace std;#define maxn 30typedef struct{ int x, y; int w;}edge;edge e[maxn * maxn / 2];int rank_[maxn], father[maxn], sum;int cmp(edge a, edge b){ // return a.w < b.w;}void make_set(int x){ father[x] = x; rank_[x] = 0;}int find_set(int x){ return x != father[x] ? find_set(father[x]) : father[x];}void union_set(int x, int y, int w){ if(x == y) return ; if(rank_[x] > rank_[y]) father[y] = x; else{ if(rank_[x] == rank_[y]) rank_[y]++; father[x] = y; } sum += w; //}int main(){ int n, m, k, weight, i, j; char a, b; while(scanf("%d", &n) && n){ k = 0, sum = 0; for(i = 0; i < n - 1; i++){ cin >> a >> m, make_set(a - 'A'); for(j = 0; j < m; j++){ cin >> b >> weight, make_set(b - 'A'); e[k].x = a - 'A', e[k].y = b - 'A'; e[k++].w = weight; } } sort(e, e + k, cmp); for(i = 0; i < k; i++) union_set(find_set(e[i].x), find_set(e[i].y), e[i].w); printf("%d\n", sum); } return 0;}
转载地址：http://zskxi.baihongyu.com/