题意：N个村庄（N<100），给出每两个村庄之间的距离，求找这N个村庄连通的最短距离和。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233
——>>这是用来试试最小生成树的Kruskal与Prim算法的增强信心的好题呀……我用Kruskal
#include <iostream>
#include <queue>using namespace std;const int maxn = 100 + 10; //N ( < 100 )
struct node //结点数据类型
{int v1; //其中一个村庄int v2; //另一个村庄int dis; //两个村庄之间的距离bool operator < (const node &v) const //为优先队列重载运算符{return dis > v.dis;}
};
int fa[maxn], sum; //并查集用的fa数组与最终目标sumint find_set(int x) //并查集查找
{if(x == fa[x]) return x;else{fa[x] = find_set(fa[x]);return fa[x];}
}
bool union_set(node n) //并查集合并
{int root_v1 = find_set(n.v1);int root_v2 = find_set(n.v2);if(root_v1 == root_v2) return 0;else{fa[root_v2] = root_v1;sum += n.dis;return 1;}
}
int main()
{int N, i;node no;while(cin>>N){if(!N) return 0;for(i = 1; i <= N; i++) fa[i] = i; //初始化priority_queue<node> pq; //为Kruskal算法用的优先队列int bor = N*(N-1)/2;for(i = 0; i < bor; i++){cin>>no.v1>>no.v2>>no.dis;pq.push(no);}sum = 0;while(!pq.empty()){no = pq.top();pq.pop();union_set(no);}cout<<sum<<endl;}return 0;
}