10034 - Freckles

[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

[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

[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?

[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

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

[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

[xenon]

Thanks even, now I also get PE by adding just one writeln statement!
This is really stupid. The judges should look into it.

[DreamLinuxer]

what's the change after rejudge????

[Ivan Golubev]

Now it has multiple input, read the description.

[DreamLinuxer]

Now it has multiple input, read the description.

appreciate your help

[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]

[htl]

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

[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;
}

[htl]

Thanks very much.

[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[i],&y[i]);
for(i=0,k=0;i<n;i++) {
for(j=i+1;j<n;j++) {
dx=x[i]-x[j];
dy=y[i]-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[i]='0';
n--;
i=0;
cost=0;
while(n>0) {
if(status[e[i].v1]=='0' || status[e[i].v2]=='0') {
cost+=e[i].cost;
status[e[i].v1]='1';
status[e[i].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]