[c]

/* @JUDGE_ID: 45892CA 10147 C "MST - Prim" */

#include <stdio.h>

#define MAXTOWNS 750

#define MAXEXISTING 1000

#define BIG 999999999

typedef struct

{

int x, y;

} dot;

typedef struct

{

int towns[MAXTOWNS];

int ntowns;

} vertex;

dot existing[MAXEXISTING], mini[MAXTOWNS][MAXTOWNS];

vertex vertices[MAXTOWNS];

int ntowns, nexisting, nvertices;

double cd[MAXTOWNS][MAXTOWNS], d[MAXTOWNS][MAXTOWNS];

double distance(int, int, int, int);

void connect_vertices();

void calc_distance();

void mst_prim();

int main()

{

int cases, i, j, c;

dot towns[MAXTOWNS];

scanf("%d", &cases);

for (c = 0; c < cases; c++)

{

scanf("%d", &ntowns);

for (i = 0; i < ntowns; i++)

scanf("%d %d", &towns

*.x, &towns*

*.y);*

scanf("%d", &nexisting);

for (i = 0; i < nexisting; i++)

{

scanf("%d %d", &existingscanf("%d", &nexisting);

for (i = 0; i < nexisting; i++)

{

scanf("%d %d", &existing

*.x, &existing**.y);*

existingexisting

*.x--; existing**.y--;*

}

/* calculate the cartesian distance */

for (i = 0; i < ntowns; i++)

for (j = i; j < ntowns; j++)

if (i == j)

cd}

/* calculate the cartesian distance */

for (i = 0; i < ntowns; i++)

for (j = i; j < ntowns; j++)

if (i == j)

cd

*[j] = 0;*

else cdelse cd

*[j] = cd[j]**= distance(towns**.x, towns[i].y,*

towns[j].x, towns[j].y);

/* consider the connected vertices as one vertex & calculate dist*/

connect_vertices();

calc_distance();

if (nvertices == 1)

printf("No new highways need\n");

else

mst_prim();

if (c < cases - 1) printf("\n");

}

return 0;

}

double distance(int x1, int y1, int x2, int y2)

{

return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

}

void connect_vertices()

{

int i, j, k, nt, state, was[MAXTOWNS], put[MAXTOWNS][MAXTOWNS];

memset(was, 0, sizeof(was));

memset(vertices, 0, sizeof(vertices));

memset(put, 0, sizeof(put));

nvertices = 0;

for (i = 0; i < ntowns; i++)

if (!was[i])

{

vertices[nvertices].towns[vertices[nvertices].ntowns] = i;

vertices[nvertices].ntowns++;

put[nvertices][i] = 1;

state = 1;

while (state)

{

state = 0;

nt = vertices[nvertices].ntowns;

for (j = 0; j < nt; j++)

{

for (k = 0; k < nexisting; k++)

{

if (existing[k].x == vertices[nvertices].towns[j])

if (!was[existing[k].y] &&

!put[nvertices][existing[k].y])

{

vertices[nvertices].towns[vertices[nvertices].ntowns]

= existing[k].y;

vertices[nvertices].ntowns++;

state = 1;

put[nvertices][existing[k].y] = 1;

}

if (existing[k].y == vertices[nvertices].towns[j])

if (!was[existing[k].x] &&

!put[nvertices][existing[k].x])

{

vertices[nvertices].towns[vertices[nvertices].ntowns]

= existing[k].x;

vertices[nvertices].ntowns++;

state = 1;

put[nvertices][existing[k].x] = 1;

}

}

was[vertices[nvertices].towns[j]] = 1;

}

}

nvertices++;

}

}

void calc_distance()

{

int i, j, k, l, mink, minl;

double min;

for (i = 0; i < nvertices; i++)

for (j = i; j < nvertices; j++)

if (i == j)

d[i][j] = 0, mini[i][j].x = i, mini[i][j].y = j;

else

{

min = BIG;

for (k = 0; k < vertices[i].ntowns; k++)

for (l = 0; l < vertices[j].ntowns; l++)

if (cd[vertices[i].towns[k]][vertices[j].towns[l]] < min)

{

min = cd[vertices[i].towns[k]][vertices[j].towns[l]];

mink = k;

minl = l;

}

d[i][j] = d[j][i] = min;

mini[i][j].x = mini[j][i].x = vertices[i].towns[mink];

mini[i][j].y = mini[j][i].y = vertices[j].towns[minl];

}

}

void mst_prim()

{

int key[MAXTOWNS], was[MAXTOWNS], pi[MAXTOWNS];

int i, j, k, u, v;

double min;

for (i = 0; i < nvertices; i++)

key[i] = BIG, was[i] = 0, pi[i] = -1;

key[0] = min = 0;

while (min != BIG)

{

min = BIG;

for (i = 0; i < nvertices; i++)

if (!was[i] && key[i] < min)

min = key[i], u = i;

was = 1;

for (v = 0; v < nvertices; v++)

if (!was[v] && d[v] != 0)

if (d[v] < key[v])

key[v] = d[v], pi[v] = u;

}

for (k = 1; k < nvertices; k++)

printf("%d %d\n", mini[pi[k]][k].x + 1, mini[pi[k]][k].y + 1);

}

[/c]

After studying your posts for a while, I came to a conclusion that Kruskal's algorithm is much more suitable for this problem (which is actually an easy problem).towns[j].x, towns[j].y);

/* consider the connected vertices as one vertex & calculate dist*/

connect_vertices();

calc_distance();

if (nvertices == 1)

printf("No new highways need\n");

else

mst_prim();

if (c < cases - 1) printf("\n");

}

return 0;

}

double distance(int x1, int y1, int x2, int y2)

{

return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

}

void connect_vertices()

{

int i, j, k, nt, state, was[MAXTOWNS], put[MAXTOWNS][MAXTOWNS];

memset(was, 0, sizeof(was));

memset(vertices, 0, sizeof(vertices));

memset(put, 0, sizeof(put));

nvertices = 0;

for (i = 0; i < ntowns; i++)

if (!was[i])

{

vertices[nvertices].towns[vertices[nvertices].ntowns] = i;

vertices[nvertices].ntowns++;

put[nvertices][i] = 1;

state = 1;

while (state)

{

state = 0;

nt = vertices[nvertices].ntowns;

for (j = 0; j < nt; j++)

{

for (k = 0; k < nexisting; k++)

{

if (existing[k].x == vertices[nvertices].towns[j])

if (!was[existing[k].y] &&

!put[nvertices][existing[k].y])

{

vertices[nvertices].towns[vertices[nvertices].ntowns]

= existing[k].y;

vertices[nvertices].ntowns++;

state = 1;

put[nvertices][existing[k].y] = 1;

}

if (existing[k].y == vertices[nvertices].towns[j])

if (!was[existing[k].x] &&

!put[nvertices][existing[k].x])

{

vertices[nvertices].towns[vertices[nvertices].ntowns]

= existing[k].x;

vertices[nvertices].ntowns++;

state = 1;

put[nvertices][existing[k].x] = 1;

}

}

was[vertices[nvertices].towns[j]] = 1;

}

}

nvertices++;

}

}

void calc_distance()

{

int i, j, k, l, mink, minl;

double min;

for (i = 0; i < nvertices; i++)

for (j = i; j < nvertices; j++)

if (i == j)

d[i][j] = 0, mini[i][j].x = i, mini[i][j].y = j;

else

{

min = BIG;

for (k = 0; k < vertices[i].ntowns; k++)

for (l = 0; l < vertices[j].ntowns; l++)

if (cd[vertices[i].towns[k]][vertices[j].towns[l]] < min)

{

min = cd[vertices[i].towns[k]][vertices[j].towns[l]];

mink = k;

minl = l;

}

d[i][j] = d[j][i] = min;

mini[i][j].x = mini[j][i].x = vertices[i].towns[mink];

mini[i][j].y = mini[j][i].y = vertices[j].towns[minl];

}

}

void mst_prim()

{

int key[MAXTOWNS], was[MAXTOWNS], pi[MAXTOWNS];

int i, j, k, u, v;

double min;

for (i = 0; i < nvertices; i++)

key[i] = BIG, was[i] = 0, pi[i] = -1;

key[0] = min = 0;

while (min != BIG)

{

min = BIG;

for (i = 0; i < nvertices; i++)

if (!was[i] && key[i] < min)

min = key[i], u = i;

was = 1;

for (v = 0; v < nvertices; v++)

if (!was[v] && d[v] != 0)

if (d[v] < key[v])

key[v] = d[v], pi[v] = u;

}

for (k = 1; k < nvertices; k++)

printf("%d %d\n", mini[pi[k]][k].x + 1, mini[pi[k]][k].y + 1);

}

[/c]

After studying your posts for a while, I came to a conclusion that Kruskal's algorithm is much more suitable for this problem (which is actually an easy problem).