讨论 / 你索它为嘛过不了!!!
Ackermann 2016-08-01 21:26:27
点我顶贴 收藏 删除
#include<cstdio>

int m,n,num(0),Num(0),i[10001],X[10001],Y[10001],f[10001]={0};

long long sum(0),ans(0);

int Find(int t)

{

if (!f[t])

return t;

f[t]=Find(f[t]);

return f[t];

}

void Qsort(int t1,int t2)

{

int x=t1,y=t2,m=i[(t1+t2)>>1],t;

do

{

while (i[x]<m)

x++;

while (i[y]>m)

y--;

if (x<=y)

{

t=i[x];

i[x]=i[y];

i[y]=t;

t=X[x];

X[x]=X[y];

X[y]=t;

t=Y[x];

Y[x]=Y[y];

Y[y]=t;

x++;

y--;

}

}

while (x<=y);

if (x<t2)

Qsort(x,t2);

if (t1<y)

Qsort(t1,y);

}

int main()

{

scanf("%d%d",&n,&m);

for (int a=1;a<=m;a++)

{

int t,t1,t2;

scanf("%d%d%d",&t1,&t2,&t);

sum+=t;

i[++num]=t;

X[num]=t1;

Y[num]=t2;

}

Qsort(1,n);

for (int a=1;a<=m;a++)

{

int t1,t2;

t1=Find(X[a]);

t2=Find(Y[a]);

if (t1!=t2)

{

ans+=i[a];

f[t2]=t1;

Num++;

if (Num==n-1)

{

printf("%I64d",sum-ans);

break;

}

}

}

return 0;

}

查看更多回复
提交回复