为了学习最小生成树 这两天学习了并查集 做并查集的题碰到了一道最小生成树 自己搞定了这道题 非常的高兴哈~
#include < iostream > #include < stdio.h > #include < algorithm > using namespace std; int father[ 101 ]; void makeset( int n){ for ( int i = 1 ;i <= n;i ++ ) { father[i] = i; }} int findset( int x){ if (father[x] != x) { father[x] = findset(father[x]); } return father[x];} int Union( int a, int b){ int x = findset(a); int y = findset(b); if (x == y) return 1 ; // 如果两个点在同一颗树中 那么这两个点添加以后会形成回路 返回1 else { father[x] = y; return 0 ; }} struct country{ int first; int second; int distance;}a[ 5001 ]; bool cmp(country x,country y){ return x.distance < y.distance;} int main(){ int n; while (scanf( " %d " , & n) != EOF) { if (n == 0 ) break ; makeset(n); int sum = 0 ; for ( int i = 1 ;i <= n * (n - 1 ) / 2 ;i ++ ) { scanf( " %d %d %d " , & a[i].first, & a[i].second, & a[i].distance); } sort(a + 1 ,a + n * (n - 1 ) / 2 + 1 ,cmp); // 将距离从小到大的排序 for ( int i = 1 ;i <= n * (n - 1 ) / 2 ;i ++ ) { if (Union(a[i].first,a[i].second) == 0 ) // 如果两个点在同一颗树中 那么这两个点添加以后会形成回路 否则这两个点之间的路加入到最小生成树中 sum = sum + a[i].distance; } printf( " %d\n " ,sum); } return 0 ;}转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048239.html
相关资源：JAVA上百实例源码以及开源项目