Page **1** of **7**

### 10034 - Freckles

Posted: **Tue Aug 06, 2002 9:48 am**

by **xenon**

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

Posted: **Tue Aug 06, 2002 10:01 am**

by **Dominik Michniewski**

I use Prim algorithm too, but I use to implement it priority queue and got accepted ... maybe try to change your code in this way ?

your code looks the same (at first look)

Greetings

Posted: **Tue Aug 06, 2002 10:49 am**

by **xenon**

Does 'Priority cue' mean sorting the distances first? I can see that that would improve the speed, but not the outcome. I don't think speed is a factor here, because my program WA's in 0.000 seconds.

Something else must be wrong. Could rounding be an issue?

Posted: **Tue Aug 06, 2002 11:33 am**

by **Dominik Michniewski**

I don't think, that precision error should be a problem. I didn't worry about that....

I use queue to insert distances, which I found, in right place ... it's a kind of insertion sort for first loop

and Prim works like BFS with this priority queue ...

maybe this help you

### hi...xenon

Posted: **Fri Aug 16, 2002 8:25 pm**

by **Even**

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...=.=....

Posted: **Sat Aug 17, 2002 3:10 am**

by **broderic**

hmm, very strange. I had the exact same problem as xenon

with constant WA's...print a newline after the last case, and you get

PE. What I don't understand is how that can result in WA?

thanks for the tip

broderick

Posted: **Sat Aug 17, 2002 7:28 am**

by **xenon**

Thanks even, now I also get PE by adding just one writeln statement!

This is really stupid. The judges should look into it.

### 10034 why runtime error?

Posted: **Tue Oct 01, 2002 3:24 pm**

by **DreamLinuxer**

what's the change after rejudge????

Posted: **Tue Oct 01, 2002 3:36 pm**

by **Ivan Golubev**

Now it has multiple input, read the description.

Posted: **Tue Oct 01, 2002 3:41 pm**

by **DreamLinuxer**

Ivan Golubev wrote:Now it has multiple input, read the description.

appreciate your help

### 10034

Posted: **Tue Oct 22, 2002 11:10 am**

by **htl**

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]

Posted: **Wed Nov 27, 2002 1:12 am**

by **htl**

I don't know why I got WA when I use the qsort function.

Posted: **Wed Nov 27, 2002 9:02 am**

by **Adrian Kuegel**

Your sort function is wrong, you don't sort integers here!!

use perhaps:

int comp(const void *a,const void *b)

{

if (((edge *)a)->len>((edge *)b)->len) return 1;

if (((edge *)a)->len<((edge *)b)->len) return -1;

return 0;

}

Posted: **Wed Nov 27, 2002 5:32 pm**

by **htl**

Thanks very much.

### 10034

Posted: **Wed Jan 15, 2003 6:00 am**

by **zsepi**

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]