各位前辈：杭电acm HDU 1233题，最简单的最小生成树问题，但我的为什么总是access violation呢

发布网友 发布时间：2022-04-24 13:56

我来回答

共2个回答

热心网友 时间：2023-10-15 08:48

access violation 一般都是数组开小了。你的代码中也就一个flag数组。。
我把你的flag数组开大之后提交下，超时了。。
楼主在自己看看把。。
超时代码。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
#include<iostream>
#include<queue>
using namespace std;
typedef struct
{
int v1,v2,len;
}Node;
bool operator >(Node a,Node b)
{
if(a.len>b.len)
return true;
else
return false;
}
bool flag[100000];
int main()
{
int n;
Node e;
priority_queue< Node,vector<Node>,greater<Node> > q;
while(scanf("%d",&n),n)
{
while(!q.empty()) q.pop();
int m = n*(n-1)/2;
int i;
for(i=0;i<n;i++)
flag[i] = false;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e.v1,&e.v2,&e.len);
q.push(e);
}
int count = 1,sum = 0;
while(count <n)
{
e = q.top();
q.pop();
if(flag[e.v1] && flag[e.v2])
continue;
flag[e.v1] = true;
flag[e.v2] = true;
sum += e.len;
count ++;
}
cout<<sum<<endl;
}
return 0;
}

热心网友 时间：2023-10-15 08:48

编号是从1到N，而你在对数组f和rank赋初始值的时候是从0到N-1赋的，也未对输入的村庄编号进行减1处理，所以会出现wrong answer的情况。你只需要将for(i=0;i<n;i++)改为for(i=1;i<=n;i++)或对所有输入的村庄编号进行减1处理就能Accepted。
修改后的程序如下(这段程序采用的修改是将for(i=0;i<n;i++)改为for(i=1;i<=n;i++)):
#include<stdio.h>
#include<stdlib.h>
#define N 105
#define MAX 50005
typedef struct{
int x,y,cost;
}edge;
edge s[MAX];
int ans,f[N],rank[N];
int cmp(const void *a,const void *b)
{
return ((edge *)a)->cost-((edge *)b)->cost;
}
void make_set(int x)
{
f[x]=x;
rank[x]=0;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void Union(int x,int y,int cost)
{
ans+=cost;
if(rank[x]>rank[y])
f[y]=x;
else
{
if(rank[x]==rank[y])
rank[y]++;
f[x]=y;
}
}
int main()
{
int i,n,k,x,y;
while(scanf("%d",&n),n!=0)
{
for(k=0;k<n*(n-1)/2;k++)
scanf("%d%d%d",&s[k].x,&s[k].y,&s[k].cost);
qsort(s,k,sizeof(s[0]),cmp);
for(i=1;i<=n;i++)
make_set(i);
ans=0;
for(i=0;i<k;i++)
{
x=find(s[i].x);
y=find(s[i].y);
if(x!=y)
Union(x,y,s[i].cost);
}
printf("%d\n",ans);
}
return 0;
}