OJ Board

why WA??

Could anyone send me some test data??

Thank you very much

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct edges
{
int v1;
int v2;
double length;
}Edge;

int comp(const void *a,const void *b)
{
if (((Edge *)a)->length > ((Edge *)b)->length) return 1;
if (((Edge *)a)->length < ((Edge *)b)->length) return -1;
return 0;
}

int link[750];

int Find(int element)
{
if(link[element]==element)
return element;
else
return Find(link[element]);
}

void UnionSet(int set1, int set2)
{
link[set2]=set1;
}

void Union(int element1, int element2)
{
UnionSet(Find(element1),Find(element2));
}

void Kruskal(Edge *e,int nt,int ne,int nb)
{
int y=0;
qsort(e,ne,sizeof(Edge),comp);
nt-=nb;
while(nt>1)
{
if(Find(e[y].v1)!=Find(e[y].v2))
{
printf("%d %d\n",e[y].v1+1,e[y].v2+1);
Union(e[y].v1,e[y].v2);
nt--;
}
y++;
}
}

int main()
{
Edge e[300000];
int pos[750][2],NumT,x,y,z,count,NumE,NumB,t1,t2;
scanf("%d",&count);
for(x=0;x<count;x++)
{
/* get data */
scanf("%d",&NumT);
for(y=0;y<NumT;y++)
{
scanf("%d %d",&pos[y][0],&pos[y][1]);
link[y]=y;
}

scanf("%d",&NumB);

if((NumB+1)>=NumT)
{
for(y=0;y<NumB;y++)
{
scanf("%d %d",&t1,&t2);
}
printf("No new highways need\n\n");
continue;
}

for(y=0;y<NumB;y++)
{
scanf("%d %d",&t1,&t2);
Union(t1-1,t2-1);
}

/* compute the distance */
NumE=0;
for(y=0;y<NumT;y++)
for(z=y+1;z<NumT;z++)
{
e[NumE].v1=y;
e[NumE].v2=z;
e[NumE++].length=sqrt((pos[y][0]-pos[z][0])*(pos[y][0]-pos[z][0])+(pos[y][1]-pos[z][1])*(pos[y][1]-pos[z][1]));
}

Kruskal(e,NumT,NumE,NumB);
printf("\n");
}
return 0;
}
[/cpp]

I had solved this problem, Thank you

Can the town number be outputed interchangeably ?

For example ,
1 6
3 7
4 9
5 7
8 3

Can it be (also sorted):
1 6
3 7
3 8
5 7
9 4

?

Or even need not be sorted ?

Did you see green checkmark ?
That means, that this problem avoids this .... don't worry about this - any correct solution should be accepted ...

Bets regards
DM

Hi!

Does anyone know why my code SIGSEGVs (invalid memory reference)? I use Kruskal's algorithm.

Here's the code:
[c]
#include <stdio.h>

#define MAXTOWNS 750
#define MAXHIGHWAYS 1000

#define min2(A, B) ((A < B) ? (A) : (B))
#define max2(A, B) ((A > B) ? (A) : (B))

typedef struct
{
int x, y;
} dot;

typedef struct
{
int x, y;
double w;
} edge;

edge edges[MAXTOWNS * MAXTOWNS];
dot existing[MAXHIGHWAYS], build[MAXTOWNS];
int connections[MAXTOWNS];
int towns, highways, nexisting, nbuild, nedges;

/* calculate the distance in Cartesian coordinate system */
double distance(dot a, dot b)
{ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }

int cmp(const void *e1, const void *e2)
{
double w1, w2;

w1 = ((const edge *)e1)->w; w2 = ((const edge *)e2)->w;

if (w1 < w2) return -1;
else if (w1 > w2) return 1;
else return 0;
}

void mst_kruskal()
{
int i, j, l, min, max;

for (i = 0; i < towns; i++)
connections = i;

for (i = 0; i < nexisting; i++)
{
max = max2(existing.x, existing.y);
min = min2(existing.x, existing.y);

connections[max] = min;
}

l = nbuild = 0;

for (i = 0; l < towns - nexisting - 1; i++)
{
if (l >= towns) break;
if (connections[edges.x] != connections[edges.y])
{
l++;

build[nbuild].x = edges.x;
build[nbuild].y = edges.y;
nbuild++;

min = min2(connections[edges.x], connections[edges[i].y]);
max = max2(connections[edges[i].x], connections[edges[i].y]);

for (j = 0; j < towns; j++)
if (connections[j] == max)
connections[j] = min;
}
}
}

int main()
{
int i, j;
dot coordinates[MAXTOWNS], a, b;

while (scanf("%d", &towns) == 1)
{
for (i = 0; i < towns; i++)
scanf("%d %d", &coordinates[i].x, &coordinates[i].y);

if (scanf("%d", &nexisting) != 1) break;
for (i = 0; i < nexisting; i++)
{
scanf("%d %d", &existing[i].x, &existing[i].y);
existing[i].x--, existing[i].y--;
}

nedges = 0;

for (i = 0; i < towns - 1; i++)
for (j = i + 1; j < towns; j++)
{
edges[nedges].x = i;
edges[nedges].y = j;
edges[nedges].w = distance(coordinates[i], coordinates[j]);
nedges++;
}

/* sort the edges */
qsort(edges, nedges, sizeof(edge), cmp);

mst_kruskal();

for (i = 0; i < nbuild; i++)
printf("%d %d\n", build[i].x + 1, build[i].y + 1);
}

return 0;
}
[/c]

Thanks in advance!

-- Tomislav Novak

It's a multiple input problem.

Tomislav Novak wrote:Hi!

Does anyone know why my code SIGSEGVs (invalid memory reference)? I use Kruskal's algorithm.

Here's the code:
[c]
#include <stdio.h>

#define MAXTOWNS 750
#define MAXHIGHWAYS 1000
/*...*/
edge edges[MAXTOWNS * MAXTOWNS];
dot existing[MAXHIGHWAYS], build[MAXTOWNS];
int connections[MAXTOWNS];
[/c]

As UFP2161 already pointed out this is a multiple input problem.

I'd suggest also to be more careful with the sizing of the arrays.
For example the index of the connections array as defined is in the range 0,(MAXTOWNS-1) which is definitely short by one.

Ciao!!!

Claudio

Thanks.

I've fixed that, but now I get TLE (I suppose checking for connectedness is too slow).

Anyway, can this problem also be solved using Prim's algorithm?

Anyway, can this problem also be solved using Prim's algorithm?

Of course it can. I solved this problem using Prim's algorithm.


Anggakusuma

angga888 wrote:Of course it can. I solved this problem using Prim's algorithm.

Could you explain me how? I don't understand how can i continue spanning the tree using Prim's algorithm...

Some (pseudo) code would be appreciated

look at the following link:

http://students.ceid.upatras.gr/~papage ... t/prim.htm

shamim wrote:look at the following link:

Still nothing...
I know how to do a classic Prim (like in 10034, Freckles), but this is giving me a headache
I've tried with where u and v are towns connected by already built highways... That way edge u-v is always part of the MST. My solution printed for the test case given in the problem description, and the correct output given is (i have 3 5, and correct is 3 7)

Ofcourse, judge said WA

Hi Tomislav,

Tomislav Novak wrote:I know how to implement Prim's algorithm, but I have trouble when some edges are already given and I have to continue spanning the MST (like in this problem)...

You can try this way:
- Assume that cities which have already been connected by given highways as one vertex.
- Also assume another cities without any highways as one vertex.
- With this assumption, every vertex will consist of one or more city. And each vertex is free from the others (no highways connected each vertex).
- To build new highways, implement Prim's algorithm as usual by only considering those vertex. So, now you don't need to be confused with the given highways.

Let me give you an example:
For the sample input, the existing highways are 1 3, 9 7, 1 2.
By following the first step mentioned above, you will get:
vertex 1 : 1 2 3 -> because they are all connected each others
vertex 2 : 7 9 -> same as above
Now, the second step will give you:
vertex 3 : 4
vertex 4 : 5
vertex 5 : 6
vertex 6 : 8
Now run the prim's algorithm with only considering 6 vertexs, and you will get the minimal possible total length of new highways.

Not a fast solution, but at least I did this way and got AC.


Anggakusuma

angga888 wrote: You can try this way:
- Assume that cities which have already been connected by given highways as one vertex.
- Also assume another cities without any highways as one vertex.
- With this assumption, every vertex will consist of one or more city. And each vertex is free from the others (no highways connected each vertex).
- To build new highways, implement Prim's algorithm as usual by only considering those vertex. So, now you don't need to be confused with the given highways.

Let me give you an example:
For the sample input, the existing highways are 1 3, 9 7, 1 2.
By following the first step mentioned above, you will get:
vertex 1 : 1 2 3 -> because they are all connected each others
vertex 2 : 7 9 -> same as above
Now, the second step will give you:
vertex 3 : 4
vertex 4 : 5
vertex 5 : 6
vertex 6 : 8
Now run the prim's algorithm with only considering 6 vertexs, and you will get the minimal possible total length of new highways.

Not a fast solution, but at least I did this way and got AC.

I can't say I quite understand this... I'm using adjacency matrix d... So if 1, 2, 3 are already connected, I should set d[1][2] = d[1][3] = d[2][3] = 0 (zero means that distance between u and v is 0, i.e. vertices are connected; d[v] is the distance between u and v in Cartesian coordinate system)? That seems slow, and I think it wouldn't work anyway

Also I don't understand how can I assume more vertices (cities) as one vertex

Code please!

Tomislav Novak wrote:Also I don't understand how can I assume more vertices (cities) as one vertex

you can assume more than one cities as one vertex.

Let me continue my example:
vertex 1 : 1 2 3
vertex 2 : 7 9
vertex 3 : 4
vertex 4 : 5
vertex 5 : 6
vertex 6 : 8
Assume that dis[city1][city2] is the cartesian distance between city1 and city2.
Btw, you should still going with my assumption about the difference between vertex and city. Example above: vertex 1 consist of city1, city2, and city3.

Now, create an adjacency matrix (say way[][]) to store the distance between vertices.
So way[1][2] is the distance between vertex 1 and vertex 2, and the exact value will be minimum(dis[1][7],dis[1][9],dis[2][7],dis[2][9],dis[3][7],dis[3][9]).
Same with way[1][3]=minimum(dis[1][4],dis[2][4],dis[3][4]).
And so on... you will get the distance between all vertices.
From now on, you have an adjacency matrix of 6 vertices (matrix way[][]), and you may forget matrix dis[][] (because this matrix is no longer useful).
Next, run the prim's algorithm using matrix way[][] as the distance between vertices.

Try it... I hope it is clear enough.


Anggakusuma