10147  Highways
Moderator: Board moderators

 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 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(t11,t21);
}
/* 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]
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(t11,t21);
}
/* 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]

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
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 ?
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 ?

 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
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)
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]
Thanks in advance!
 Tomislav Novak
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
Re: 10147 "Highways"  runtime error (SIGSEGV)
As UFP2161 already pointed out this is 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]
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,(MAXTOWNS1) which is definitely short by one.
Ciao!!!
Claudio
 Tomislav Novak
 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
 Tomislav Novak
 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
 Tomislav Novak
 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
Still nothing...shamim wrote:look at the following link:
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;
Code: Select all
4 9
3 5
1 6
5 7
3 8
Code: Select all
1 6
3 7
4 9
5 7
8 3
Ofcourse, judge said WA
Hi Tomislav,
 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
You can try this way: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)...
 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
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 anywayangga888 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.
Also I don't understand how can I assume more vertices (cities) as one vertex
Code please!
you can assume more than one cities as one vertex.Tomislav Novak wrote:Also I don't understand how can I assume more vertices (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