10147 - Highways

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10147 - Highways

Post by Chow Wai Chung » Sat May 17, 2003 9:19 am

why WA?? :x

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]

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

Post by Chow Wai Chung » Wed May 28, 2003 3:02 am

I had solved this problem, Thank you

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

10147 unclear output format

Post by route » Mon Jul 28, 2003 6:21 pm

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:

Post by Dominik Michniewski » Tue Jul 29, 2003 9:39 am

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)

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

10147 "Highways" - runtime error (SIGSEGV)

Post by Tomislav Novak » Thu May 20, 2004 4:55 pm

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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri May 21, 2004 5:40 am

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)

Post by CDiMa » Fri May 21, 2004 10:23 am

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

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

Post by Tomislav Novak » Fri May 21, 2004 2:30 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?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon May 31, 2004 8:36 pm

Anyway, can this problem also be solved using Prim's algorithm?
Of course it can. I solved this problem using Prim's algorithm. :wink:


Anggakusuma

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

Post by Tomislav Novak » Tue Jun 08, 2004 2:18 pm

angga888 wrote:Of course it can. I solved this problem using Prim's algorithm. :wink:
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 :)

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jun 08, 2004 4:17 pm


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

Post by Tomislav Novak » Wed Jun 09, 2004 4:47 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 :(

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Fri Jun 11, 2004 7:45 am

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. :wink:


Anggakusuma

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

Post by Tomislav Novak » Fri Jun 11, 2004 12:43 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. :wink:
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! ;)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Fri Jun 11, 2004 4:45 pm

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. :wink:


Anggakusuma

Post Reply

Return to “Volume 101 (10100-10199)”