## 10147 - Highways

Moderator: Board moderators

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

### 10147 - Highways

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 Find(int element)
{
return element;
else
}

void UnionSet(int set1, int set2)
{
}

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;
int pos,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],&pos[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]-pos[z])*(pos[y]-pos[z])+(pos[y]-pos[z])*(pos[y]-pos[z]));
}

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

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong
I had solved this problem, Thank you

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

### 10147 unclear output format

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 ?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

### 10147 "Highways" - runtime error (SIGSEGV)

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]

-- Tomislav Novak

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
It's a multiple input problem.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10147 "Highways" - runtime error (SIGSEGV)

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

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
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?

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Anyway, can this problem also be solved using Prim's algorithm?
Of course it can. I solved this problem using Prim's algorithm. Anggakusuma

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
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 shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
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

Code: Select all

``````distance[u][v] = -1;
``````
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

Code: Select all

``````4 9
3 5
1 6
5 7
3 8
``````
for the test case given in the problem description, and the correct output given is

Code: Select all

``````1 6
3 7
4 9
5 7
8 3
``````
(i have 3 5, and correct is 3 7)

Ofcourse, judge said WA angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
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 = d = d = 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! angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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 is the distance between vertex 1 and vertex 2, and the exact value will be minimum(dis,dis,dis,dis,dis,dis).
Same with way=minimum(dis,dis,dis).
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