UVA上也交了，官方数据也测了，都是对的。。
谁能告诉我问什么在这里Wrong Answer?
#include <stdio.h>
#include <math.h>
#include <string.h>

#define maxn 800

struct Tpoint{int x,y;};
struct Tedge{double len;int a,b;};
Tpoint town[maxn];
Tedge g[maxn][maxn],ans[maxn];
int n,m,count,tot,casenum,father[maxn],color[maxn];

double getdist(Tpoint a,Tpoint b)
{
  double x=a.x-b.x,y=a.y-b.y;
  return sqrt(x*x+y*y);
}

int findset(int x)
{
  if (father[x]==x) return x;
  father[x]=findset(father[x]);
  return father[x];
}

void unionset(int x,int y)
{
  int rootx,rooty;
  rootx=findset(x); rooty=findset(y);
  father[rootx]=rooty;
}

void init()
{
  int i,j,a,b,roota,rootb,colora,colorb,now;
  double len;
  scanf("%d",&n);
  for (i=1;i<=n;i++) {
    scanf("%d%d",&town[i].x,&town[i].y);
    father[i]=i;
  }
  count=n;
  scanf("%d",&m);
  for (i=1;i<=m;i++) {
    scanf("%d%d",&a,&b);
    roota=findset(a); rootb=findset(b);
    if (roota!=rootb) {
      unionset(roota,rootb);
      count--;
    }
  }
  now=0;
  for (i=1;i<=n;i++)
    if (father[i]==i) color[i]=++now;
  for (i=1;i<=count;i++)
    for (j=1;j<=count;j++) {
      g[i][j].len=100000000;
      g[i][j].a=g[i][j].b=-1;
    }
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++) {
      roota=findset(i); rootb=findset(j);
      colora=color[roota]; colorb=color[rootb];
      if (roota!=rootb) {
        len=getdist(town[i],town[j]);
        if (len<g[colora][colorb].len) {
          g[colora][colorb].len=g[colorb][colora].len=len;
          g[colora][colorb].a=i; g[colora][colorb].b=j;
          g[colorb][colora].a=i; g[colorb][colora].b=j;
        }
      }
    }
}

void work()
{
  double dist[maxn];
  bool used[maxn];
  int i,j,min,father[maxn];
  tot=0;
  memset(used,false,sizeof(used));
  used[1]=true;
  for (i=2;i<=count;i++) {
    father[i]=1;
    dist[i]=g[1][i].len;
  }
  for (i=2;i<=count;i++) {
    min=-1;
    for (j=1;j<=count;j++)
      if (!used[j] && (min==-1 || dist[j]<dist[min])) min=j;
    ans[++tot]=g[father[min]][min];
    used[min]=true;
    for (j=1;j<=count;j++)
      if (!used[j] && (g[min][j].len<dist[j])) {
        father[j]=min;
        dist[j]=g[min][j].len;
      }
  }
}

void print()
{
  int i;
  if (count==1) printf("\n");
  else for (i=1;i<=tot;i++)
         printf("%d %d\n",ans[i].a,ans[i].b);
}

int main()
{
  scanf("%d",&casenum);
  while (casenum--) {
    init();
    work();
    print();
    if (casenum) printf("\n");
  }
  return 0;
}

• 你仔细看一下输入输出，uva改了原题，我没改的 (2777) hawk 2004-08-20 08:09:06
  • Re:你仔细看一下输入输出，uva改了原题，我没改的 (4) yuewuren 2005-07-13 20:59:26
    • Re:你仔细看一下输入输出，uva改了原题，我没改的 (35) mao_mato 2005-07-13 22:26:02
      • Re:你仔细看一下输入输出，uva改了原题，我没改的 (7) xfxyjwf 2005-07-14 04:51:22