10034 - Freckles
Moderator: Board moderators
10034 - Freckles
This looks like a basic application of Prim's algo, and that's how I treat it. But I keep getting WA. Can anybody point me to my mistake?
[pascal]program p10034(input,output);
{SPOILER DELETED}
[/pascal]
Thanks so much,
-xenon
[pascal]program p10034(input,output);
{SPOILER DELETED}
[/pascal]
Thanks so much,
-xenon
Last edited by xenon on Sat Aug 17, 2002 7:24 am, edited 1 time in total.
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
hi...xenon
hello....xenon...
you can try to print one blank line after the last case...
for this stupid bug...I try Kruskal and Prim and spend two hours on it...
finally, I mark off my last line ( if( T ) puts("") )...
just like your ( if (caseno > 1) then writeln ; )
and then...it work...=.=....
you can try to print one blank line after the last case...
for this stupid bug...I try Kruskal and Prim and spend two hours on it...
finally, I mark off my last line ( if( T ) puts("") )...
just like your ( if (caseno > 1) then writeln ; )
and then...it work...=.=....
-
- New poster
- Posts: 8
- Joined: Tue Oct 01, 2002 3:22 pm
10034 why runtime error?
what's the change after rejudge????
Last edited by DreamLinuxer on Tue Oct 01, 2002 3:39 pm, edited 1 time in total.
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
-
- New poster
- Posts: 8
- Joined: Tue Oct 01, 2002 3:22 pm
10034
I just use simple Kruskal algo. But it keeps getting WA. I even read my friend's code and still can't find out the bug. What's wrong with my code?
[c]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SQUARE(x) ((x)*(x))
typedef struct edges
{
int v1,v2;
double len;
}edge;
int comp(const void*,const void*);
void main(void)
{
int count,x,y,z,a,n,set[100],temp;
double pos[100][2],sum;
edge e[5000];
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
scanf("%d",&n);
for(y=0;y<n;y++)
scanf("%lf %lf",&pos[y][0],&pos[y][1]);
a=0;
for(y=0;y<n;y++)
for(z=y+1;z<n;z++)
e[a].v1=y,e[a].v2=z,e[a++].len=sqrt(SQUARE(pos[y][0]-pos[z][0])+SQUARE(pos[y][1]-pos[z][1]));
qsort(e,a,sizeof(edge),comp);
for(y=0;y<n;y++)
set[y]=y;
for(y=0,sum=0;y<a;y++)
if(set[e[y].v1]!=set[e[y].v2])
{
temp=set[e[y].v1];
for(z=0;z<n;z++)
if(set[z]==temp)
set[z]=set[e[y].v2];
sum+=e[y].len;
}
printf("%.2lf\n",sum);
}
}
int comp(const void *a,const void *b)
{
return ((edge *)a)->len-((edge *)b)->len;
}
[/c]
[c]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SQUARE(x) ((x)*(x))
typedef struct edges
{
int v1,v2;
double len;
}edge;
int comp(const void*,const void*);
void main(void)
{
int count,x,y,z,a,n,set[100],temp;
double pos[100][2],sum;
edge e[5000];
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
scanf("%d",&n);
for(y=0;y<n;y++)
scanf("%lf %lf",&pos[y][0],&pos[y][1]);
a=0;
for(y=0;y<n;y++)
for(z=y+1;z<n;z++)
e[a].v1=y,e[a].v2=z,e[a++].len=sqrt(SQUARE(pos[y][0]-pos[z][0])+SQUARE(pos[y][1]-pos[z][1]));
qsort(e,a,sizeof(edge),comp);
for(y=0;y<n;y++)
set[y]=y;
for(y=0,sum=0;y<a;y++)
if(set[e[y].v1]!=set[e[y].v2])
{
temp=set[e[y].v1];
for(z=0;z<n;z++)
if(set[z]==temp)
set[z]=set[e[y].v2];
sum+=e[y].len;
}
printf("%.2lf\n",sum);
}
}
int comp(const void *a,const void *b)
{
return ((edge *)a)->len-((edge *)b)->len;
}
[/c]
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
10034
honestly, if someone could explain me why on earth I get runtime error with this problem, would appreciate it... thanx
[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MX 101
typedef struct _edge {
int v1,v2;
double cost;
}edge;
edge e[5001];
double x[MX],y[MX];
int compare(const void *a, const void *b) {
double x;
edge *i,*j;
i=(edge *)a;
j=(edge *)b;
x=i->cost-j->cost;
if(x==0.0) return 0;
else if(x>0) return 1;
else return -1;
}
void getData(int n) {
int i,j,k;
double dx,dy;
for(i=0;i<n;i++) scanf("%lf %lf",&x,&y);
for(i=0,k=0;i<n;i++) {
for(j=i+1;j<n;j++) {
dx=x-x[j];
dy=y-y[j];
e[k].v1=i;
e[k].v2=j;
e[k].cost=sqrt(dx*dx+dy*dy);
k++;
}
}
qsort(e,k,sizeof(edge),compare);
}
void kruskal(int n) {
char status[n];
int i;
double cost=0.0;
for(i=0;i<n;i++) status='0';
n--;
i=0;
cost=0;
while(n>0) {
if(status[e.v1]=='0' || status[e.v2]=='0') {
cost+=e.cost;
status[e.v1]='1';
status[e.v2]='1';
n--;
}
i++;
}
printf("%.2lf\n",cost);
}
main() {
int N,n;
scanf("%d",&N);
while(N-->0) {
scanf("%d",&n);
getData(n);
kruskal(n);
if(N!=0) printf("\n");
}
}[/c]
[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MX 101
typedef struct _edge {
int v1,v2;
double cost;
}edge;
edge e[5001];
double x[MX],y[MX];
int compare(const void *a, const void *b) {
double x;
edge *i,*j;
i=(edge *)a;
j=(edge *)b;
x=i->cost-j->cost;
if(x==0.0) return 0;
else if(x>0) return 1;
else return -1;
}
void getData(int n) {
int i,j,k;
double dx,dy;
for(i=0;i<n;i++) scanf("%lf %lf",&x,&y);
for(i=0,k=0;i<n;i++) {
for(j=i+1;j<n;j++) {
dx=x-x[j];
dy=y-y[j];
e[k].v1=i;
e[k].v2=j;
e[k].cost=sqrt(dx*dx+dy*dy);
k++;
}
}
qsort(e,k,sizeof(edge),compare);
}
void kruskal(int n) {
char status[n];
int i;
double cost=0.0;
for(i=0;i<n;i++) status='0';
n--;
i=0;
cost=0;
while(n>0) {
if(status[e.v1]=='0' || status[e.v2]=='0') {
cost+=e.cost;
status[e.v1]='1';
status[e.v2]='1';
n--;
}
i++;
}
printf("%.2lf\n",cost);
}
main() {
int N,n;
scanf("%d",&N);
while(N-->0) {
scanf("%d",&n);
getData(n);
kruskal(n);
if(N!=0) printf("\n");
}
}[/c]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.