HDU 1102 Constructing Roads 最小生成树

解题报告：要使N个村庄之间都连通，现在已知有一些村庄之间已经连通了，现在在要使所有的村庄都连通，问最少需要的修的路是多少？

感觉这题好坑，prim已知过不了，但是改了克鲁斯卡尔就过了，觉得应该是题目数据有问题。一个简单的题，注意别用prim就是了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct node {
    int front ,rear,length;
}Rode[10000];
int N,Q,tot,a,b,d,par[105];
bool cmp(node R1,node R2) {
    return R1.length < R2.length;
}

int find(int i) {
    return i==par[i]? i:par[i] = find(par[i]);
}

int main( ) {
    while(scanf("%d",&N)!=EOF) {
        int k = 0;
        for(int i = 1;i<=N;++i)
        for(int j = 1;j<=N;++j) {
            scanf("%d",&d);
            if(i >1 && j < i)
            Rode[++k].front = i,Rode[k].rear = j,Rode[k].length = d;
        }
        for(int i = 1;i<=N;++i)
        par[i] = i;
        scanf("%d",&Q);
        while(Q--) {
            scanf("%d%d",&a,&b);
            par[find(a)] = find(b);
        }
        sort(Rode+1,Rode+k+1,cmp);
        int tot = 0;
        for(int i = 1;i<=k;++i) {
            int x = find(Rode[i].front);
            int y = find(Rode[i].rear);
            if(x != y) {
                tot += Rode[i].length;
                par[x] = y;
            }
        }
        printf("%d
",tot);
    }
    return 0;
}