本蒟蒻面对这道最小生成树时,深感无力,用Kruskal编写的程序样例过了但测试点全部WA
真就青草池塘处处WA
代码如下 求助!!!
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,w;
}e[10005];
int n,k,f[10005],cnt,cont,cunt;
bool cmp(node xp,node yp)
{
return xp.w<yp.w;
}
int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
int main()
{
memset(e,0,sizeof(e));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
}
sort(e+1,e+k+1,cmp);
for(int i=1;i<=k;i++)
{
if(find(e[i].x)!=find(e[i].y))
{
f[e[i].x]=find(e[i].y);
cnt+=e[i].w;
cont++;
}
if(cont==n-1)
{
break;
}
}
for(int i=1;i<=k;i++)
{
cunt+=e[i].w;
}
printf("%d",cunt-cnt);
return 0;
}
谢谢各位大佬的帮助!!!