最短路问题杂谈

感觉这类问题好多变形，记录一下，方便复习。

P1522 [USACO2.4] 牛的旅行 Cow Tours

由于题目的N很小，且要求任意两点之间距离，很容易想到一下暴力做法：

1. 求出题目的联通块，记id[u]为点u的连通块编号；
2. 枚举任意两个无序点对（j从i+1开始），连接它们，用floyd算法跑出最短路，暴力求出该牧场的直径并更新答案。

该暴力做法时间复杂度为\(O(N+M)+O(N^2 \times N^3)=O(N^5)\)，显然会超时。

这时就要用最短路问题的常用套路了：不要每次都跑一次最短路，一开始跑一次，后面通过查表加推式子的方式来统计答案。
所以我们先在原图上跑一次最短路。

照样枚举点对，考虑优化新牧场的直径的变化。新牧场一定是两个旧牧场合并来的。所以新牧场直径有可能是老的两个牧场的直径，也有可能是通过新加入的这条边的一条路径。
新加入的边\((x,y)\)所在最长路径就是分别从\(x\)和\(y\)出发，在原牧场最远的距离加上\(distance(x,y)\)。

CODE

原文地址：http://www.cnblogs.com/zhangchenxin/p/16852053.html