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
题意：
给出小农区的坐标，和一个邻接矩阵，表示农区的连接情况。要求挑两个农区用一条边连接起来。使得它们的直径最小。（直径是相距最远的两个点的距离）
代码如下：
/*
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)//计算两点间的直接距离
{
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;//两点间没有边或没有直接连起来的权值为-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;//对给出的数据求两点的距离
}
}
}
}
void Floyd(int 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)//将能连接点求距离。
{
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)//对连同分量标记颜色
{
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)//寻找同个连通分量里点x到其他点的最长距离
{
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)//农民只需要挑两个农场，使得连接起来后的直径是最小的。
{
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]);//假设连线
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);//连同分量的个数
FindPath(n, num);
Floyd(n);
printf("%lf\n", FindMax(n));
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}