http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2336
题目大意:(如题)
输入输出:(如题)
解题思路:
1.参考了nocow-usaco上的解题思路,开辟数组len,len[i][j]表示牧区i到牧区j的最短距离。maxlen[i]表示牧区i到其他可到达牧区的最大距离。
2.首先输入数据,p[i]保存了各个牧区的坐标,所以当:
(1)输入的字符为1时,对应的牧区i和牧区j的距离即可求出,公式为:
sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
(2)输入的字符为0时,设置为距离MAX表示无穷大;
(3)i等于j时表示是同一个牧区,所以距离为0。
3.然后用Floyd-Warshall算法进行连通片距离的更新,代码如下:

for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(len[i][k]+len[k][j]<len[i][j])
					len[i][j]=len[i][k]+len[k][j];

4.更新后记录牧区i到其他可达牧区的最大距离
5.然后就是两个牧区的连接操作了,选出len数组中距离为MAX的两个牧区进行连接,然后选出中间距离最小的一个。
6.最后与原来已经求出的maxlen数组中的距离进行比较,选出最大的一个,即为所求

发表评论

电子邮件地址不会被公开。

Post Navigation