1023: [SHOI2008]cactus仙人掌图

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 1440  Solved: 582

[][][]

Description

如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

 

举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。

Input

输入的第一行包括两个整数n和m（1≤n≤50000以及0≤m≤10000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

Output

只需输出一个数，这个数表示仙人图的直径长度。

Sample Input

15 3

9 1 2 3 4 5 6 7 8 3

7 2 9 10 11 12 13 10

5 2 14 9 15 10 8

10 1

10 1 2 3 4 5 6 7 8 9 10

Sample Output

9

HINT

 

对第一个样例的说明：如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。

 

【注意】使用Pascal语言的选手请注意：你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M 5000000}，其中5000000即指代栈空间的大小，请根据自己的程序选择适当的数值。

 

Source

题解：妈了个鸡。。。我都会了动态仙人掌了结果这种傻叉DP都不会= =我有没有救了天哪。。。留个坑吧。。。

题解在这里：http://z55250825.blog.163.com/blog/static/150230809201412793151890/

 

首先咱们的总思想是DFS出一棵树，然后在DFS的过程中求出答案。

  现在只考虑DFS出的这棵树，原图的不是树上的边我们称为非树边。然后每个节点的深度定义为DFS树中的深度。

  我们设 F[i] 表示DFS树中以 i 为根的子树的点及i在仙人掌图的诱导子图中（诱导子图就是由某个图的一个点集V及所有两个端点都在集合V中的边构成的边集E构成的图）的 以i为起点到诱导子图内其他各点的最短路径中的最长的一条的长度。

 

  这个定义貌似ydc神犇没有讲太清（肯定是太简单了咩！）...所以咱蒟蒻一开始也是各种误解和YY.....感觉上就是这样的吧...

  首先，假设某一条非树边(u,v)，它显然是将u,v在其DFS树上的路径连成一个环，由于仙人图的性质，这条路径上的边必定不会出现在另一个环，所以咱们可以把它分割出来，这样整张图实际上就是一个又一个的环以及它们之间的连边（这个就是桥）或者直接相连。

  以上是一些YY的性质，现在咱们先考虑没有环的情况....

  那么咱们的答案，即这个最远点对的 路径 可能是怎样构成的？

  首先来看一个结论：

  1.该路径必然存在一个且只有一个节点，它在这条路径的所有点中深度最小（咱们称之为最高点）。

   这个很好理解，假设这条路径存在两个节点u,v，它们深度相同且最小，那么请问它们两个是如何相连的？首先不可能是因为爱情，它们连向它们的父亲（它们的父亲深度比它们还小，可是咱们假设的是它们的深度就是路径所有点最小的，所以这样它们父亲就不在路径中，矛盾），接下来也不可能是它们之间连边（假设它们之间连了边，那么我们DFS其中一个点u的时候，按照DFS的流程，必然可以先DFS出另一个点，使它的深度是u的深度+1，这与它们深度相同矛盾），更不可能是它们的后代连的边（假设它们的后代连了边，且我们是先DFS u 的，那么我们就可以从u的后代DFS到达v的后代然后DFS到v，即可以在u的后代中搜到v, 所以u,v不可能深度相同，矛盾）

 所以咱们知道这样一个性质，那么就是每一条路径都对应到这个路径的最高点，这个节点在这个路径中深度最小。那么，对于每一个节点 w，我们都可以得到这样的路径的集合，它们都对应该节点 w。

 那么咱们只需要求出每一个节点对应的路径的集合中最长的一条即可，然后把每一个节点的答案取最大即可。

 那么我们一开始设的F[]就还是有用的。

 先是 F[ ] 的转移

  F [ i ] =max(F [ k ]) +1(k∈i的儿子）

 而这个集合中最长的路径就是儿子中F最大的+儿子中F第二大的+2  

 这个的转移有个技巧，我们按 u 的儿子依次dfs下去，递归求出儿子们的F, 然后每 dfs 完一个儿子，我们用 F[u]+F[v]+W[u][v]更新答案，然后再用 F[v]+w[u][v] 更新 F[u]，这里题目不要求w[u][v]=1。

  但是上面讨论的仅仅是没有环的情况，非树边咱们并没有考虑进去。    

  而由1的证明咱们知道，每一条非树边都只能由一个祖先连向它的后代（这应该很显然把，反证一下即可）。我们考虑一个祖先u和它的后代v的非树边构成的环。

  

   先假设只出现一个环吧...而且就是根节点到某个节点u,（比如下图，红色边为非树边，它构成了1，2，3的环），那么咱们该怎么做？

   

    首先可以发现这个图实际上可以变成这个样子...

    

    也就是说三个点这个时候其实就地位平等了....即对于环上的各个点，它们实际上都是地位平等的。我们选出环上的最高点作为代表元，将这个环的一些信息放在这个代表元上，然后往上传递即可。这个信息就是最高点的F。算法的大体思想大致是这样吧...

    我们来看看新增加了环之后咱们要做些什么。

   首先，咱们在搜索完节点u的孩子v的时候，如果判断出u和v在同一个环上，且u不是最高点，那么咱们就不用F[u]+F[v]+1来更新答案，直接跳过搜索其他儿子，也就是说，待我们搜索完所有儿子之后，这个时候我们的节点u的F，实际上存的就是所有和u不在同一环上的儿子所连出来的最短路径中的最长的，而和u在同一环上的没有考虑，然后更新的答案也只是用所有和u不在同一环上的儿子所形成的最长路和次短路更新，也没有处理环。所以处理完儿子的DFS之后，咱们再开始处理环。现在来看看如何处理环。

 

    首先发现环的时候咱们有两个东西就不太靠谱了，一个是F ，显然F表示的最短路的最长的，这里从祖先u新出来一条边连接到后代去，可能会强行使原来u的最长的最短路径链变短，可能这条链就被原来的次短链给替代，所以咱们处理环的时候得更新F，而由于这个环的最高点的祖先们在DFS的过程中是等着它的信息来更新，这个环的后代节点的信息跟它们的改变无关，所以咱们只要保证环上节点的F正确性就可以了。根据F的定义，加了这条成环的边之后唯一会影响的便是环的最高点的F（因为其他点的诱导子图并没有改变，所以F也没有变），所以咱们要更新的也就是最高点的F。

  对于每一个环上的非最高点的节点，我们保存它们的F，实际上每一个点就保存了从它延伸下去的最短路径中的最长链。咱们可以利用这个来更新 最高点的 F。

  那么怎么更新？

  实际上模型就是 

  一个环，除了最高点u之外，每一个环上的点 有一个链（可以没有），然后要乃选出一个点v≠u，且dist(u,v)(u与v的最小距离)+链的长度F(v)(就是一条路径）最大，然后用这个最大值更新u的F，然后这个就直接环形DP就可以了...

  为什么这样是正确的？首先每一个决策都是一条路径，可以保证的就是除了顶点之外的其它节点v的F 都是 v到其儿子的最短路径中的最长路径，那么我们只要保证 u到v也是条最短路径的，那么就可以保证这个用来转移的路径也是一条最短路径，那么就可以保证这个F是合法的。然后取其中的最大值显然就是F[u]的新值。

   以上咱们维护了F[]，那么还得更新答案。刚才只是说了对于DFS树内部的咱们枚举下最高点然后DP就可以了。但是答案并涉及到没有去用走到环的路径。

   所以处理环之前对于环上的每一个点，我们更新的答案只是每一个除环以外的次长和最长路径之和，我们还得用通过环上的路径更新答案，这个时候同理我们对每一个点保留最长路即可。现在开始考虑环。对于环，实际上每一个点都是平等的，所以我们的任务就是枚举 环上的节点i ，对于节点i，当初咱们更新答案的时候只使用了i的非树边的儿子，而由于环上每一个点实际上是平等的，所以我们用环上每一个点的链去更新它，然后我们用它的 非环路的最长链F[i] 加上 到环上某个点j的最长路，加上j的最长链F[j] 来更新答案。实际上我们要求的就是 max(dist(i,j)+F(j))（F(i)是固定的），所以这个也可以用DP做...，至于做的方法嘛，dist(i,j)肯定是单增的，所以咱们用单调队列维护F（j）即可。

 

  那么一个根节点作为最高点连着多个环呢？显然这些环之间也是相互独立的，一个个环处理即可。

  

  那么不只一个环，不只根节点有环呢？注意咱们是DFS的...所以肯定是先处理儿子再处理父亲，所以咱们肯定能先递归到只有一个环的儿子处理，处理完之后这个儿子的下面就可以看做一坨链了...(环什么的没有意义了，只有它的F 有意义），然后递归回去就又是一个根节点的一坨环的问题，结果就可以了。

   

   总之这道题目 题解说的各种意识流，这里蒟蒻口胡加各种名词混乱...如果有问题求批评...求批评下手轻咩 = =...

  

   最后再来总结一下算法流程：

   1.Tarjan，记录DFS树的父亲。

 

   2.Tarjan过程中，用3的方法判断某个儿子是不是和这个点构成环，如果没有则用这个儿子更新ans。

 

   3.Tarjan返回前扫描下所有的邻接点，如果发现某个后代的父亲不是自己，说明出现环，这个环的起点就是这个点

（即环的最高点就是这个点），终点就是那个后代，然后从这个后代沿着DFS树父亲往上走的所有点都在环上，咱们把所有点取出来DP这个环。

 

   4.关于如何DP，首先咱们更新答案，然后再更新最高点的F以传递给DFS树更上面的点。更新答案实际上就是 max（F[i]+F[j]+dist(i,j)）其中dist(i,j)为点i与点j在环上的最短距离，然后咱们可以固定i ，求对于每一个i的max (F[j]+dist(i,j))，dist(i,j)等于 min(j-i,n-i+j)，为了丢掉这个min好使用单调队列，咱们将环复制一遍，然后每一次只考虑半个环长度的DP，这显然是正确的，每一个状态都可以在 i 或者 j 的时候被计算到。那么方程可以继续改写为 max（F[i]+F[j]+j-i)，固定i之后就是求 max(F[j]+j)(j∈[i+1,i+n/2]），这个单调队列无压力，所以ans就更新完了。

 

  然后就是F[最高点]的更新。这个直接枚举环上点一遍即可，环的数目总共只有O(M)的复杂度无压力。