本文共 1348 字,大约阅读时间需要 4 分钟。
#include#include using namespace std;#define maxn 20typedef struct{ int x, y; int w;}edge;edge e[maxn];int rank_[maxn], father[maxn], sum;int cmp(edge a, edge b){ //按权值非降序排序(相同则按x坐标) if(a.w == b.w) return a.x < b.x; 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){ sum += w; if(x == y) return ; if(rank_[x] > rank_[y]) father[y] = x; else{ if(rank_[x] == rank_[y]) rank_[y]++; father[x] = y; }}int main(){ int n, x, y, i; char cx, cy; freopen("kruskal.txt", "r", stdin); scanf("%d", &n); getchar(); for(i = 0; i < n; i++){ scanf("%c%c %d", &cx, &cy, &e[i].w); getchar(); e[i].x = cx -'A', e[i].y = cy - 'A'; make_set(i); //0对应于A } sort(e, e + n, cmp); //for(i = 0; i < n; i++) printf("%c-%c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); //printf("\n"); sum = 0; for(i = 0; i < n; i++){ x = find_set(e[i].x), y = find_set(e[i].y); if(x != y){ printf("%c-%c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); union_set(x, y, e[i].w); } } printf("total: %d\n", sum); return 0;}
数据文件:
实验结果: