Cow Tours
Farmer John has a number of pastures on his farm. Cow paths
connect some pastures with certain other pastures, forming a field.
But, at the present time, you can find at least two pastures that
cannot be connected by any sequence of cow paths, thus partitioning
Farmer John's farm into multiple fields.
Farmer John would like add a single a cow path between one pair
of pastures using the constraints below.
A field's `diameter' is defined to be the largest distance of
all the shortest walks between any pair of pastures in the field.
Consider the field below with five pastures, located at the points
shown, and cow paths marked by lines:
15,15 20,15
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
10,10 15,10 20,10
The `diameter' of this field is approximately 12.07106, since
the longest of the set of shortest paths between pairs of pastures
is the path from A to E (which includes the point set {A,B,E}). No
other pair of pastures in this field is farther apart when connected
by an optimal sequence of cow paths.
Suppose another field on the same plane is connected by cow paths
as follows:
*F 30,15
/
_/
_/
/
*------
G H
25,10 30,10
In the scenario of just two fields on his farm, Farmer John would
add a cow path between a point in each of these two fields (namely
point sets {A,B,C,D,E} and {F,G,H}) so that the joined set of
pastures {A,B,C,D,E,F,G,H} has the smallest possible diameter.
Note that cow paths do not connect just because they cross each
other; they only connect at listed points.
The input contains the pastures, their locations, and a symmetric
"adjacency" matrix that tells whether pastures are connected
by cow paths. Pastures are not considered to be connected to
themselves. Here's one annotated adjacency list for the pasture
{A,B,C,D,E,F,G,H} as shown above:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
Other equivalent adjacency lists might permute the rows and
columns by using some order other than alphabetical to show the
point connections. The input data contains no names for the points.
The input will contain at least two pastures that are not connected
by any sequence of cow paths.
Find a way to connect exactly two pastures in the input with a
cow path so that the new combined field has the smallest possible
diameter of any possible pair of connected pastures. Output that
smallest possible diameter.
PROGRAM NAME: cowtour
INPUT FORMAT
| Line 1: |
An integer, N (1 <= N <= 150), the
number of pastures |
| Line 2-N+1: |
Two integers, X and Y (0 <= X ,Y<=
100000), that denote that X,Y grid location of the pastures;
all input pastures are unique. |
| Line N+2-2*N+1: |
lines, each containing N
digits (0 or 1) that represent the adjacency matrix
as described above, where the rows' and columns' indices are
in order of the points just listed. |
SAMPLE INPUT (file cowtour.in)
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT FORMAT
The output consists of a single line with the diameter of the newly
joined pastures. Print the answer to exactly six decimal places. Do not
perform any special rounding on your output.
SAMPLE OUTPUT (file cowtour.out)
22.071068
題意：
給出小農(nóng)區(qū)的坐標(biāo)，和一個(gè)鄰接矩陣，表示農(nóng)區(qū)的連接情況。要求挑兩個(gè)農(nóng)區(qū)用一條邊連接起來。使得它們的直徑最小。（直徑是相距最遠(yuǎn)的兩個(gè)點(diǎn)的距離）
代碼如下：
/*
LANG: C
TASK: cowtour
*/
#include<stdio.h>
#include<math.h>
double D[150][150];
char adj[150][150];
int lo[150][2], c[150], len[150], C[150][150];
double dis(int i, int j)//計(jì)算兩點(diǎn)間的直接距離
{
int x1, y1, x2, y2;
x1 = lo[i][0], y1 = lo[i][1], x2 = lo[j][0], y2 = lo[j][1];
return sqrt(1.0 *(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) );
}
void Setdis(int n)
{
int i, j;
double d;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i == j)
{
D[i][j] = 0;
}
else
{
D[i][j] = -1;//兩點(diǎn)間沒有邊或沒有直接連起來的權(quán)值為-1
}
}
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (j > i && adj[i][j] == '1')
{
d = dis(i, j), D[i][j] = d, D[j][i] = d;//對給出的數(shù)據(jù)求兩點(diǎn)的距離
}
}
}
}
void Floyd(int n)//求任意兩點(diǎn)間的最短路徑
{
int i, j, k;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i != j && D[i][k] > 0 && D[k][j] > 0)//將能連接點(diǎn)求距離。
{
if (D[i][j] < 0)
{
D[i][j] = D[i][k] + D[k][j];
}
else if (D[i][j] > D[i][k] + D[k][j])
{
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}
}
void Colour(int n, int x, int colour)//對連同分量標(biāo)記顏色
{
int i;
for (i = 0; i < n; i++)
{
if (D[x][i] >= 0 && c[i] == -1)
{
c[i] = colour;
C[colour][len[colour]++] = i;
Colour(n, i, colour);
}
}
}
int SetColour(int n)
{
int i, j, colour;
for (i = 0; i < n; i++)//-1表示沒被著色過
{
c[i] = -1, len[i] = 0;
}
for (i = 0, colour = 0; i < n; i++)
{
if (c[i] == -1)
{
Colour(n, i, colour++);
}
}
return colour;
}
double Find(int x, int n)//尋找同個(gè)連通分量里點(diǎn)x到其他點(diǎn)的最長距離
{
int i;
double dd = 0;
for (i = 0; i < n; i++)
{
if (c[i] == c[x] && dd < D[x][i])
{
dd = D[x][i];
}
}
return dd;
}
void FindPath(int n, int num)//農(nóng)民只需要挑兩個(gè)農(nóng)場，使得連接起來后的直徑是最小的。
{
int i, j, x, y, k;
double min, pre, d, total;
min = 1000000000.0;
for (k = 0; k < num - 1; k++)
{
for (i = 0; i < len[k]; i++)
{
for (j = 0; j < len[k + 1]; j++)
{
d = dis(C[k][i], C[k+1][j]);//假設(shè)連線
total = d + Find(C[k][i], n) + Find(C[k+1][j], n);
if (min > total)
{
min = total, x = C[k][i], y = C[k + 1][j], pre = d;
}
}
}
}
D[x][y] = pre;
}
double FindMax(int n)//找兩者最長的，即求出兩者之間的半徑
{
int i, j;
double max = 0;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (max < D[i][j])
{
max = D[i][j];
}
}
}
return max;
}
int main()
{
freopen("cowtour.in", "r", stdin);
freopen("cowtour.out", "w", stdout);
int n, i, num;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d%d", &lo[i][0], &lo[i][1]);
}
for (i = 0; i < n; i++)
{
scanf("%s", adj[i]);
}
Setdis(n);
Floyd(n);
num = SetColour(n);//連同分量的個(gè)數(shù)
FindPath(n, num);
Floyd(n);
printf("%lf\n", FindMax(n));
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}