poj1258 我用krusal做的,不知道错哪了
题目链接:http://poj.org/problem?id=1258
题目大意,给出一个矩阵表明两点之间的距离,求一最小生成树
我不知道我错哪了,请高手指点
#include <iostream>
#include <stdio.h>
#include <cstring>
#define Max 0x7f7f7f7f
using namespace std;
int n;
int a[105][105];
int sum=0;
int set[105];
int findset(int x)
{
if(x==set[x])
return set[x];
else return findset(set[x]);
}
void merge (int a,int b)
{
set[a]=set[b];
}
void krusal()
{
sum=0;
for(int i=1;i<=n;i++)//
{
set[i]=i;
}
for(int i=1;i<=n;i++)
{
int min=Max;
int x,y;
for(int j=1;j<=n;j++)
{
if(a[i][j]<min && a[i][j]>0)
{
x=findset(i);
y=findset(j);
if(x!=y)
{
min=a[i][j];
merge(x,y);
sum=sum+min;
}
}
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
krusal();
printf("%d\n",sum);
}
return 0;
}
[解决办法]
并查集写的不对
[解决办法]
kruskal算法最小生成树,的一个前提是,边长是按从小到大的顺序排过序的。
LZ显然是没有排过序就用了Find和merge。
先排序,再做!希望对LZ有所帮助。