USACO/cowtour

来自NOCOW

[编辑] 一种简单高效的解法

pasture是牧场，field是片区，下面那位朋友大概是弄混了。我觉得exactly是强调边的连接方法的。而且题目刚开始说"multiple fields"，应该不一定只有两个片区。

不要被下面的说法误导了，题目有很一句重要的话“Find a way to connect exactly two pastures in the input with a cow path ”，意思是输入只包含 2 个field，最终找出一条路径把它们连接起来，那么可以考虑使用并查集（Disjoint Set）+ Floyd，其中并查集判断是否在一个 field中，全部0.02秒内求解

注意：题目里说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.所以可以不止两个连通field

[编辑] 错误的解法

求出连通片先，然后Floyd-Warshall算法求每个连通片的‘直径’，顺便记录连通片内的顶点到其他顶点的最大距离。

事实上，任意加入一条连接两个连通片C1,C2的边e之后，顶点对分为三类：均在C1中，均在C2中，或一个在C1中一个在C2中。前两者的距离的最大值是C1，C2的‘直径’，最后这类边均经过e=(v1,v2)，设v1在C1中，v2在C2中，则此类边的最大长度为C1中的顶点到v1的最大距离＋e的长度＋C2中的顶点到v2的最大距离。而这两个最大距离，在用Floyd-Warshall算法求’直径‘时，就已经得到了，只需存下来即可。因此，判断加边之后的‘直径’的可在O(n^2)时间内完成。

参见blackco3的C++代码。其中，求‘直径’可以不区分连通片，直接在整个矩阵上求解，编码上简单一些。

== 下面的部分章节可能侵犯了版权

[编辑] 分析

用Floyd求出任两点间的最短路，然后求出每个点到所有可达的点的最大距离，记做mdis[i]。（Floyd算法）

r1=max(mdis[i])

然后枚举不连通的两点i,j，把他们连通，则新的直径是mdis[i]+mdis[j]+(i,j)间的距离。

r2=min(mdis[i]+mdis[j]+dis[i,j])其中i属于牧场C1,j属于牧场C2.
re=max(r1,r2)

re就是所求。

 注意：上面的算法并不完善！^{[需要证实]}

 一组简单的数据

5

0 0

0 1

1 0

100 100

200 200

00000

00100

01000

00001

00010

正确的答案应该是2.414214，而上面的算法得到的却是141.421356.

造成这结果的原因是：

每次尝试连接并比较，得到的新的牧场的直径应该是下面三个值的最大值：

1.节点i、j连接后，得到的新通路的长度(half[i]+half[j]+sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])))；

2.原节点i所在牧场的直径dia[i]；

3.原节点j所在牧场的直径dia[j]。

其中2、3应先与1比较得出最大值，在与目前最优答案比较得出最小值。即ans={min{max{dia[i],dia[j],half[i]+half[j]+dis(i,j)}},其中i,j属于V,(i,j)不属于E} Usaco的数据一般比较强，这次也出现了疏忽。这一题数据较弱，我大小于号打反，竟然过了6个点。

完善过的code（代码）已给出。

不知道这个完善是谁给出的,首先这个数据本身不对,一个数据只有2个牧场,而这个数据有3个!!!数据本身不对,何谈完善!(以下是题目片断)

输入文件“只”包括两个不连通的牧区。请编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。

上面朋友提到的那段话，英文原文是"at least two pastures that are not connected by any sequence of cow paths"，就是“至少有两个牧场不连通”，而并没有提到有几个片区。

                                           -----Zhoushich

 修正：1、定义i点到i点的距离为0，即i可以到达i点。
       2、将原图中可以相互连通的牧区定义到同一集合中，求答案时枚举不在同一集合中的任意两点。
          新直径即为min（mdis[i]+mdis[j]+(i,j)间的距离），无需加反例中的判断。

 提醒一下，联通后的片区的直径有可能还是没联通之前的直径！不判断的话第七个测试点会报错。
 根据题意，片区应该是不止两个的，但是USACO的数据并没有顾及到这点。

求解：如果有多个牧场，那么最后输出的是任意两个牧场之间的最长路径的最大值还是最小值？题意害死人啊！！

最小值，题目说的是“最小可能直径”。直径定义就是“……的最长路径”了。

该算法没有问题，标准算法中将直径分连通片分别计算的，但是使用Folyd算法中，不连通的片是预设的MAX值，于是就不必分连通片计算直径，因为在最后比较的时候，比较的时候新加入的值只是加入一个新的边之后的值与原来连通片中的直径比较，如果已经把最大的直径求出来了，最后比较也没有错误！

                                           -----Liuking_Grey

[编辑] 给菜鸟：从最朴素到高效优化

1、你的最朴素想法是什么？

显然是利用Floyd生成原始情况，然后每条没有连接的边枚举过去，重新Floyd计算一下最大直径。

经测试，这种想法在第4个测试数据上用时近半秒，然后第5个点你等了2分钟还没有出解。

这样做，你的时间复杂度保证有O（N^5）吧？

150这个点数不容小觑啊。

2、让我们开始慢慢优化

优化1、

既然不是不同片区的两点，加上连线没有用（还出错解），那就不用加了。

用什么知道每个点属于哪个片区？方法五花八门，我用了并查集。

优化2、

预先生成所有在接下来的计算中会多次用到的数据（比如任意两点间距离）

优化3、

没意义的计算不要做了！

每条枚举的边保证编号前小后大；

   for i:=1 to n do
       for j:=i+1 to n do

如果接上这条边，预期直径比之前算到的最小直径都大就抛弃；

if dis[i,0]+pointdis[i,j]+dis[j,0]>minnum then continue//说明：dis[i,0]表示在i所在的区块内到i的最远距离【不是该区块的直径】，pointdis[i,j]表示i、j两点间直接连接的距离,minnum表示当前得到的最小直径

else floyd;

这样下来，第4个点可以秒杀了，但是第5个点（只有两个区块，随机性弱）还需要5秒+，第7个点（多区块，随机性强）需要20秒+

3、绕开错误，走向更高效

错误优化：

dis[i,0]+pointdis[i,j]+dis[j,0]>minnum

既然这个是判断条件而且也正确，那么满足这个判断条件的就可以通过dis[i,0]+pointdis[i,j]+dis[j,0]得到最短直径。

if dis[i,0]+pointdis[i,j]+dis[j,0]>minnum then continue else minnum:=dis[i,0]+pointdis[i,j]+dis[j,0];

然后很高兴，第5个超时的点秒杀，但是第7个点立刻给你摆了一道。

原因：在多区块的时候，首先，你连通的两区块的直径不一定满足dis[i,0]+pointdis[i,j]+dis[j,0]；

（2,3直连距离为1；3,4与4,5两两直连距离为2，此时最大直径为4）

（连接2,3，然后根据式子你会错误得到直径为3，其实仍为4）

其次，你联通两区块得到的新区块的直径很可能比其余区块的直径小

（1,2与2,3直连距离为1；3,4与4,5两两直连距离为2，此时最大直径为4）

（连接1,2，然后根据式子你会错误得到直径为2，其实仍为4）

正确的优化：

其实仔细想想，我们关注的只是区块的直径，那我们只需要计算新连成的区块的直径，然后与原来的所有区块的直径放在一起，取最大直径就可以了。

               tempmax:=dis[i,0]+pointdis[i,j]+dis[j,0];//计算新连成的区块的直径
               for k:=1 to n do
                   if blockdis[k]>tempmax then tempmax:=blockdis[k];//检查别的区块的直径是否比新连成的区块的直径大
               minnum:=tempmax;

然后0.2s内AC就没有任何压力了。（实现代码参见Pascal，fcxxzux1）