10147 - Highways

[Chow Wai Chung]

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]

[Chow Wai Chung]

I had solved this problem, Thank you

[route]

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]

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

[Tomislav Novak]

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

[UFP2161]

It's a multiple input problem.

[CDiMa]

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]

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]

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]

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]

look at the following link:

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

[Tomislav Novak]

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]

Hi Tomislav,

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]

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!

[angga888]

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