首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

poj1258 小弟我用krusal做的,不知道哪里错了

2012-09-06 
poj1258我用krusal做的,不知道错哪了题目链接:http://poj.org/problem?id1258题目大意,给出一个矩阵表明

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有所帮助。

热点排行