本文共 1702 字，大约阅读时间需要 5 分钟。
#include#include #include #include using namespace std;const int maxn = 75 + 5;int n, pos, m, ans, cnt;struct node{ int op; int ed; int len; bool operator < (const node Next) const { return len < Next.len; }} edge[maxn];int root[30];int Find(int x){ return root[x] == x ? x : root[x] = Find(root[x]);}void Kruskal(){ ans = 0; for(int i = 0; i <= n; i ++) root[i] = i; sort(edge, edge + pos); cnt = 0; for(int i = 0; i < pos; i ++) { int x = Find(edge[i].op); int y = Find(edge[i].ed); if(x != y) { root[y] = x; ans += edge[i].len; cnt ++; } if(cnt == n - 1) break; }}int main(){ while(~scanf("%d", & n) && n) { getchar(); pos = 0; int len; char start, city; for(int i = 0; i < n - 1; i ++) { scanf("%c", & start); scanf("%d", & m); for(int j = 0; j < m; j ++) { getchar(); scanf("%c", & city); scanf("%d", & len); edge[pos].op = start - 'A'; edge[pos].ed = city - 'A'; edge[pos].len = len; pos ++; } getchar(); } Kruskal(); printf("%d\n", ans); } return 0;}
题意：
（摘自 永夜初晗凝碧天）
在相通n个岛屿的所有桥都坏了，要重修，重修每一个桥所用的时间不同，求重修使每个岛屿都间接或直接与其他岛屿相同时所用的的最短时间（只有修完一个桥后才可修下一个桥）。简言之就是求最小生成树。 对于数据，数据输入的第一行n代表岛屿的个数，当为0是结束程序，接着n-1行开始时为这岛屿的编号，用大写字母表示，接着是一个整数m，表示与该岛屿连接的字典序大于该岛屿编号的个数，然后该行输入m对数据，每对数据的第一个字母表示与该岛屿连通的岛屿的编号，第二个数字表示要重修两岛屿之间桥所需要的时间，输出数据见样例及原题。题解：
简单的Kuskal。注意输入时要滤去空格就行。
转载地址：http://ictpi.baihongyu.com/