以下是我的代碼：
#include<stdio.h>
const long maxn=107,INF=10000007;
typedef struct
{
long u,v,w;
}edge;
long n,m,g[maxn][maxn],mst;
edge E[maxn*maxn];
long f[maxn];
long Getf(long x)
{
if(f[x]==x) return x;
f[x]=Getf(f[x]);
return f[x];
}
bool Judge(long x,long y)
{
return (Getf(x)==Getf(y));
}
void Union(long x,long y)
{
long i=Getf(x),j=Getf(y);
if(i==j) return ;
f[i]=j;
}
void Qsort(edge *a,long begin,long end)
{
long i=begin,j=end,mid=a[(begin+end)/2].w;
edge t;
do{
while(a[i].w<mid) i++;
while(a[j].w>mid) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(a,begin,j);
if(i<end) Qsort(a,i,end);
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
g[i][j]=INF;
for(long i=1;i<=m;i++)
scanf("%ld%ld%ld",&E[i].u,&E[i].v,&E[i].w);
// Read In
Qsort(E,1,m);
// Qsort
for(long i=1;i<=n;i++) f[i]=i;
// Init
mst=0;
long i=0,j=1;
while(i<n-1)
{
long a=E[j].u,b=E[j].v;
if(!Judge(a,b))
{
mst+=E[j].w;
Union(a,b);
i++;
}
j++;
}
printf("%ld\n",mst);
return 0;
}
posted on 2010-01-21 23:04
lee1r 閱讀(648)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構