牛的旅行

57 阅读 0 评论 38 点赞

我是靠谱客的博主缥缈冰棍，最近开发中收集的这篇文章主要介绍牛的旅行，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径(注意，恰好一条)。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短距离)。John在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有更小的直径。

Input

输入有多组数据，每组数据第1行：一个整数N(1<=N<=150)，表示牧区数。
第2到第N+1行：每行两个整数X,Y(0<=X,Y<=100000)，表示N个牧区的坐标，每个牧区的坐标都是不一样的。
第N+2行到第2*N+1行：每行包括N个数字(0或1)表示一个对称邻接矩阵。
输入数据中至少包括两个不连通的牧区。

Output

对于每组数据输出仅一行，一个实数表示所求答案，数字保留六位小数。

Sample Input

Sample Output

22.071068

//题解：先把所有牧区能连成牧场的全部连起来，再计算同一个牧场的以各个点为起点的最大直径，

        在计算把两个牧场连起来的最小直径，最后求各个牧场中的最大直径。

//标程：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double  p[200][200];
double x[155], y[155];
const double Max = 1e20;
double calculata(int i,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
//  	freopen("a.txt","r",stdin);
    int n, i, j, k;
	char ch;
    while(scanf("%d",&n)!=EOF)
	{
		for(i = 1; i <= n; i ++)
			scanf("%lf%lf",&x[i],&y[i]);
		for(i = 0; i <= n; i ++)
		{
			for(j = 0; j <= n; j ++)
				p[i][j] = Max;
		}
		for(i = 1; i <= n; i ++)
		{
			for(j = 1; j <= n; j ++)
			{
				cin >> ch;
				if(ch == '1')
				{
					double temp(calculata(i,j));
					if(p[i][j] > temp) p[i][j] = temp;
				}
			}
		}
		for(i = 1; i <= n; i ++)
		for(j = 1; j <= n; j ++)
		for(k = 1; k <= n; k ++)
			if(i != j && j != k && p[j][i] < Max && p[i][k] < Max)
			{
				 if(p[j][k] > p[j][i] + p[i][k])
					p[j][k] = p[j][i] + p[i][k];
			}
		double d[200], minn(Max);
		for(i = 0; i <= n; i ++) d[i] = 0;
	        for(i = 1; i <= n; i ++)
		for(j = 1; j <= n; j ++)
                    if(i != j && p[i][j] < Max && d[i] < p[i][j])
			d[i] = p[i][j];
		for(i = 1; i <= n; i ++)
		{
			for(j = 1; j <= n; j ++)
			{
				if(i != j && p[i][j] >= Max)
				{
					double temp1(calculata(i,j));
				        if(minn > d[i] + d[j] + temp1)
					     minn = d[i] + d[j] + temp1;
				}
			}
		}
		for(i = 1; i <= n; i ++)
			if(minn < d[i])   minn = d[i];
		printf("%.6lfn",minn);
	}
	return 0;
}