时间:2008-05-26 11:10:13   来源:论坛整理  作者:  编辑:chinaitzhe

谁有北大acm2421的源代码，搞来看一下，我写的程序老是WA，就是找不到错误啊。
网友回复:……还要让回帖的找题目？
网友回复:Description

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.

We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

Then there is an integer Q (0 <= Q <= N * (N 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input

3
0 990 692
990 0 179
692 179 0
1
1 2

Sample Output

179
这是题目
网友回复:就是最小生成树,prim就可以了

C/C code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/





#include <stdio.h>

#include <math.h>

#define max 999999999

int prim(int a[128][128],int n)

{    

     int i,j,k;

     int min,s=0;

     int v[128],c[128];

     for(i=2;i<=n;i  )

     {

         v[i]=a[1][i];

         c[i]=1;                

     }

     for(i=2;i<=n;i  )

     {    

         min=v[i];

         k=i;

         for(j=2;j<=n;j  )

         if(v[j]<min)

         {

              min=v[j];

              k=j;            

         }

         s=s min;

         v[k]=max;

         for(j=0;j<=n;j  )

         if(a[k][j]<v[j]&&v[j]<max)

         {

              v[j]=a[k][j];

              c[j]=k;                          

         }

     }

     return s;     

}

int main()

{

    int i,j,n,q,a[128][128],x,y;

    while(scanf("%d",&n)==1)

    {

          for(i=1;i<=n;i  )

          for(j=1;j<=n;j  )

          scanf("%d",&a[i][j]);

          scanf("%d",&q);

          for(i=0;i<q;i  )

          {

               scanf("%d%d",&x,&y);

               a[x][y]=a[y][x]=0;                

          } 

          printf("%d\n",prim(a,n));        

    }    

    return 0;

}

网友回复:我也知道啊，可就是通不过啊。
我怀疑是题意没搞懂。
Q为什么0 <=Q <=N*(N 1)/2？我认为是0 <=Q <=N*(N-1)/2
网友回复:
#include <stdio.h>
int Grape[101][101];
int u[101]={0};//保存已收录的顶点
int v[101];
int N;//村庄数
int sum=0;
int qyi()//判定顶点是否全取到了
{
int i;
int sum1=0;
for(i=1;i <=N;i )
sum1 =u[i];
if(sum1==N)
return 1;
else return 0;
}
void input()
{
int i,j;
int Q;//已有路数
int a,b;//结点
scanf("%d",&N);
for(i=1;i <=N;i )
v[i]=1;
for(i=1;i <=N;i )//输入图
for(j=1;j <=N;j )
scanf("%d",&Grape[i][j]);
scanf("%d",&Q);
if(Q==0)
{
u[1]=1;
v[1]=0;
}
else
{
for(i=0;i <Q;i )
{
scanf("%d%d",&a,&b);
if(u[a]!=1)
{
u[a]=1;
v[a]=0;
}
if(u!=1)
{
u[b]=1;
v[b]=0;
}
}
}
}
int prime()
{
int i,j;
int i1,j1;
int min;
while(!qyi())
{
min=1001;
for(i=1;i <=N;i )
{
for(j=1;j <=N;j )
if(u[i]==1&&v[j]==1)
{
if(Grape[i][j] <min&&Grape[i][j]>0)
{
min=Grape[i][j];
i1=i;
j1=j;
}
}
}
sum =min;
u[j1]=1;
v[j1]=0;
}
return sum;
}
int main()
{
input();
printf("%d\n",prime());
return 0;
}
这是我写的程序，应该没错误的，可提交老是说wrong answer.[color=#FF0000][b]
网友回复:#include <stdio.h>
int Grape[101][101];
int u[101]={0};//保存已收录的顶点
int v[101];
int N;//村庄数
int sum=0;
int qyi()//判定顶点是否全取到了
{
int i;
int sum1=0;
for(i=1;i <=N;i )
sum1 =u[i];
if(sum1==N)
return 1;
else return 0;
}
void input()
{
int i,j;
int Q;//已有路数
int a,b;//结点
scanf("%d",&N);
for(i=1;i <=N;i )
v[i]=1;
for(i=1;i <=N;i )//输入图
for(j=1;j <=N;j )
scanf("%d",&Grape[i][j]);
scanf("%d",&Q);
if(Q==0)
{
u[1]=1;
v[1]=0;
}
else
{
for(i=0;i <Q;i )
{
scanf("%d%d",&a,&b);
if(u[a]!=1)
{
u[a]=1;
v[a]=0;
}
if(u[b]!=1)
{
u[b]=1;
v[b]=0;
}
}
}
}
int prime()
{
int i,j;
int i1,j1;
int min;
while(!qyi())
{
min=1001;
for(i=1;i <=N;i )
{
for(j=1;j <=N;j )
if(u[i]==1&&v[j]==1)
{
if(Grape[i][j] <min&&Grape[i][j]>0)
{
min=Grape[i][j];
i1=i;
j1=j;
}
}
}
sum =min;
u[j1]=1;
v[j1]=0;
}
return sum;
}
int main()
{
input();
printf("%d\n",prime());
return 0;
}