测试结果1: 通过本测试点|有效耗时62ms
测试结果2: 测试结果错误.错误结果为:59271
正确结果应为:42880
测试结果3: 测试结果错误.错误结果为:59271
正确结果应为:139949
测试结果4: 测试结果错误.错误结果为:59271
正确结果应为:83199
测试结果5: 测试结果错误.错误结果为:59271
正确结果应为:165204
测试结果6: 测试结果错误.错误结果为:59271
正确结果应为:42880
测试结果7: 测试结果错误.错误结果为:59271
正确结果应为:37870
测试结果8: 测试结果错误.错误结果为:59271
正确结果应为:159982
测试结果9: 测试结果错误.错误结果为:59271
正确结果应为:50493
测试结果10: 通过本测试点|有效耗时47ms
#include"stdio.h"
#define INF 999999
int n,m,count=0,countm,a[1001]={0},cost[1001][1001];
struct E
{
int x;
int y;
int w;
}v[1001];
int cmp(const void *a,const void *b)
{
struct E *p=(struct E *)a,*q=(struct E *)b;
return p->w > q->w ? 1:-1;
}
int find(int p)
{
int r=p,temp;
while(a[r]!=0)
r=a[r];
while(a[p]!=0)
{
temp=a[p];
a[p]=r;
p=temp;
}
return r;
}
void uni(int x,int y)
{
int p,q;
p=find(x);
q=find(y);
if(p!=q)
{
if(x==p)
a[p]=q;
else
a[q]=p;
}
}
int main()
{
int i,j,x,y,w,tmp;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=INF;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
if(w<cost[x][y])
{
cost[x][y]=w;
cost[y][x]=w;
}
}
tmp=1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(cost[i][j]!=INF)
{
v[tmp].x=i;
v[tmp].y=j;
v[tmp].w=cost[i][j];
tmp++;
}
qsort(v+1,tmp-1,sizeof(v[0]),cmp);
countm=n-1;
for(i=1;i<=tmp-1;i++)
if(find(v[i].x)!=find(v[i].y))
{
count+=v[i].w;
countm--;
uni(v[i].x,v[i].y);
}
printf("%d",count);
return 0;
}
#include"stdio.h"
#define INF 999999
int n,m,count=0,countm,a[1001]={0},cost[1001][1001];
struct E
{
int x;
int y;
int w;
}v[1001];
int cmp(const void *a,const void *b)
{
struct E *p=(struct E *)a,*q=(struct E *)b;
return p->w > q->w ? 1:-1;
}
int find(int p)
{
int r=p,temp;
while(a[r]!=0)
r=a[r];
while(a[p]!=0)
{
temp=a[p];
a[p]=r;
p=temp;
}
return r;
}
void uni(int x,int y)
{
int p,q;
p=find(x);
q=find(y);
if(p!=q)
{
if(x==p)
a[p]=q;
else
a[q]=p;
}
}
int main()
{
int i,j,x,y,w,tmp;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=INF; //初始化cost[][]
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
if(w<cost[x][y]) //相同边中找权值最小的那一组
{
cost[x][y]=w;
cost[y][x]=w;
}
}
tmp=1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(cost[i][j]!=INF) //初始化v[]，即将可用边的端点和权值放入v[]
{
v[tmp].x=i;
v[tmp].y=j;
v[tmp].w=cost[i][j];
tmp++;
}
qsort(v+1,tmp-1,sizeof(v[0]),cmp); //按权值排序可用边
countm=n-1;
for(i=1;i<=tmp-1;i++)
if(find(v[i].x)!=find(v[i].y)) //找出端点不在同一连通分量的边
{
count+=v[i].w;
countm--;
uni(v[i].x,v[i].y);
}
printf("%d",count); //输出最小边权和
return 0;
}
你的数组开小了，要知道m<=n*(n-1)最大时可以为999000.v的储存上限的应该是m。
我就是这样，改大后AC…………