Question

poj1258题为何 Runtime error? 求助！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 100
#define MAX 10000000

using namespace std;

struct Edge
{
int v1,v2;
int l;
};

Edge e[N*N];
int x[N];
int cmp(const void *a,const void *b)
{
return ((Edge*)a)->l-((Edge*)b)->l;
}
int tou(int n)
{
if(x[n]==n)
return n;
return tou(x[n]);
}
void init(int n)
{
for (int i=0; i<n; ++i)
x[i]=i;
}
int main()
{
int n;
while(cin>>n)
{
init(n);
int k=0;
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
{
e[k].v1=i;
e[k].v2=j;
cin>>e[k].l;
k++;
}
qsort(e,k,sizeof(e[0]),cmp);
int toux,touy,sum=0;
for (int i=0; i<k; i+=2)
{
toux=tou(e[i].v1);
touy=tou(e[i].v2);
if(toux!=touy)
{
sum+=e[i].l;
x[toux]=touy;
}
}

cout<<sum<<endl;

}

return 0;
}
我想问问这种方法为什么交不上？
商讨一下！

Answer 1

话说你的并查集为什么要i+=2
i++就过了啊

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 100
#define MAX 10000000

using namespace std;

struct Edge
{
int v1,v2;
int l;
};

Edge e[N*N];
int x[N];

int cmp(const void *a,const void *b)
{
return ((Edge*)a)->l-((Edge*)b)->l;
}

int tou(int n)
{
if(x[n]==n)
return n;
return tou(x[n]);
}

void init(int n)
{
for (int i=0; i<n; ++i)
x[i]=i;
}
int main()
{
int n;
while(cin>>n)
{
init(n);
int k=0;
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
{
e[k].v1=i;
e[k].v2=j;
cin>>e[k].l;
k++;
}
qsort(e,k,sizeof(e[0]),cmp);
int toux,touy,sum=0;
for (int i=0; i<k; i++)
{
toux=tou(e[i].v1);
touy=tou(e[i].v2);
if(toux!=touy)
{
sum+=e[i].l;
x[toux]=touy;
}
}

cout<<sum<<endl;

}

return 0;
}