最小生成树用到并查集http://acm.hdu.edu.cn/showproblem.php?pid=1233

模板题：
不解释
[cpp] 
#include<cstdio> 
#include<algorithm> 
#include<string.h> 
#include<iostream> 
using namespace std; 
class node 
{ 
public : 
    node() 
    { 
    val=0;   
    } 
 
    bool operator<(const node x)const 
    { 
        return this->val<x.val; 
    } 
    int val; 
    int x,y; 
}; 
node a[10002]; 
int n; 
int num[10002]; 
int find(int x) 
{ 
return num[x]==x?x:num[x]=find(num[x]); 
} 
int main()   www.zzzyk.com
{ 
    while(~scanf("%d",&n)&&n) 
    { 
    node a[10002]; 
    int con=n*(n-1)/2; 
    for(int i=1;i<=con;++i) 
    { 
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val); 
        num[i]=i; 
    } 
    sort(a+1,a+con+1); 
    int sum=0; 
    //sum+=a[1].val; 
    for(int i=1;i<=con;i++) 
    { 
    int xx=find(a[i].x),yy=find(a[i].y); 
    if(xx!=yy) 
      { 
        num[xx]=yy; 
        sum+=a[i].val; 
      } 
    } 
    printf("%d\n",sum); 
    } 
return 0; 
}  

补充：软件开发 , C++ ,

上一个：poj模拟题总结（一）
下一个：左旋字符串