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(1 ~ 150),代表有 N 个坐标点(X,Y)(0 ~ 100000),后给出 N X N 的邻接矩阵,代表图的连接情况( 0 代表不相连,1 代表相连)。图明确只有两个不相连的连通块,问如何当且仅当增加一条边,使任何点对间的最短路中的最大值最小。输出这个最小数,保留六位小数。
思路:
最短路 + Floyd。先 Floyd 预处理好所有点对之间的最短路,后枚举两个点,这两个点不相连。增加这条边后,故( 第一个连通块任意两点间的最短路 + 增加边边长 + 第二个连通块任意两点间的最短路) 也为最短路,找到连接后所有点对最短路的最大值。每次枚举的最大值中找一个最小的,当找出这个最小值,还要与原来未连接的时候的最短路的最大值比较。最后得出的这个值即为最终结果的最大值。
AC:
/* TASK:cowtour LANG:C++ ID:sum-g1 */ #include <stdio.h> #include <string.h> #include <cmath> #include <algorithm> #define INF 99999999 using namespace std; typedef struct { double x,y; }node; int n; node no[155]; double w[155][155]; char state[155][155]; double max_dis; double dis (double x1,double y1,double x2,double y2) { return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); } void floyd () { for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if(w[i][k] < INF && w[k][j] < INF && w[i][j] > w[i][k] + w[k][j]) w[i][j] = w[i][k] + w[k][j]; } void init () { for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { if (state[i][j] == '1') w[i][j] = dis(no[i].x,no[i].y,no[j].x,no[j].y); else w[i][j] = INF; if(i == j) w[i][j] = 0; } } double make_max (int s,int e,double dis) { double max_now = -1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if(w[i][s] < INF && w[e][j] < INF) max_now = max(max_now,w[i][s] + w[e][j] + dis); return max_now; } int main() { freopen("cowtour.in","r",stdin); freopen("cowtour.out","w",stdout); scanf("%d",&n); for (int i = 1; i <= n; ++i) scanf("%lf%lf",&no[i].x,&no[i].y); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) scanf(" %c",&state[i][j]); } init(); floyd(); max_dis = -1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if(w[i][j] < INF) max_dis = max(max_dis,w[i][j]); double min_dis = INF; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if(w[i][j] == INF) { double change = dis(no[i].x,no[i].y,no[j].x,no[j].y); min_dis = min(min_dis,make_max(i,j,change)); } min_dis = max(min_dis,max_dis); printf("%f\n",min_dis); return 0; }
相关推荐
Web Tours 1.0.7z安装包
hp web tours 分析
Web Tours 1.0安装包下载 Web Tours是惠普 loadrunner 自带的一个飞机订票系统网站,它是一款基于ASP.net平台的网站,基于先进的.NET Framework,默认支持SqlServer数据库、Access、Mysq等多种数据库,这是基于ie、...
由于今天花了时间去移动(Loadruner自带的WebTours例子程序)到其他的电脑上,方便练习Loadrunner,偷懒。很久没有动部署的东西了,解决问题思路有些迟钝,现在把应有思路的做一个小的整理。部署高手请略过。 由于...
今天安装了Loadrunner9.0后,发现打开LR示例页面的时候会显示如下错误: Internalerror:yourrequestwasunsuccessful CannotcreateCGIprocess–programnotfound 解决方法: 打开WebTours文件夹下的run.bat,...
QTP9.2 测试工具学习的样例网站本地安装程序
早期LoadRunner培训时使用的Mercury Tours Web应用。Enjoy it!
webtours_login_success.jmx
loadrunner WebTours 示例 。不需要安装loadrunner 直接可以使用。 可以用来学习别的性能测试工具。
LoadRuner12.6实战项目,Web Tours1.0资源,有需自取,没有积分限制,原下载地址:https://marketplace.microfocus.com/appdelivery/content/web-tours-sample-application
早期LoadRunner培训时使用的Mercury Tours Web应用,太大了所以分两部分。Enjoy it!
1.启动Samples-Web-Start Web Server时,提示Could not open port 1080-Port is already used by another server(wsaeaddrinuse) 2.启动Samples-Web-Start...3.LoadRunner Sample WebTours 点击Flights出现空白解决方法
如果你忘记了某个密码,把号码输入上,去密码就破解了!
性能测试工具Lr12对应的测试系统,订票系统资源
WEB-Tours订票系统性能测试报告.docx
该文档视有关webtours案例的利用loadrunner设置检查点和事务的代码
Edmonds在1973年给出的利用匹配理论解决中国邮路问题的英文文献.
飞机订票系统。loadrunner11自带的飞机票系统,从其中进行摘取