> 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;
> }

• 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