hdu 1233 還是暢通工程（並查集+快排）

比上一道題難了那麼一丁點，嘿嘿····就是一丁點！

（天上在打雷，貌似要下雨了！是該下雨了，這幾天都熱死了，剛才去了趟WC（廁所)洗手的水都是熱的）；

本題求最短路徑，做法是先用快排，然後逐一判斷，若在同一陣營則不處理，若不在同一陣營，需歸到同一陣營，加上路程即可！

#include"algorithm"

using namespace std;

struct node
{
int x,y,z;
}a[10000];

int cmp(node a,node b)
{
return a.z<b.z;
}

int pre[100000];
int find(int k)
{
if(k==pre[k])
return k;
pre[k]=find(pre[k]);
return pre[k];
}

int main()
{
int m,i,ans,f1,f2,n;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
pre[i]=i;
m=(n-1)*n/2;
for(i=0;i<m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a,a+m,cmp);
ans=0;
for(i=0;i<m;i++)
{
f1=find(a[i].x);
f2=find(a[i].y);
if(f1!=f2)
{
pre[f1]=f2;
ans+=a[i].z;
}
}
printf("%d\n",ans);
}
return 0;
}