[树形dp][Tarjan][单调队列] Bzoj 1023 cactus仙人掌图

Description

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

 [树形dp][Tarjan][单调队列] Bzoj 1023 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
,你的任务是求出给定的仙人图的直径。

 

 

题解

  • 如果是圆圆边的话和普通的树形dp一样
  • 对于环的话,把他拎出来单独考虑,首先要计算出这个环的贡献,然后更新环的最顶点
  • 更新的话,就这个直接拿环上的点的dp值,再计算一下这两点之间的最短路,相加后更新
  • 贡献的话,就是max(f[i]+f[j]+dis(i,j)),dis(i,j)=min(abs(deep[i]-deep[j]),size[环]-abs(deep[i]-deep[j]))
  • 可以维护一个单调队列,按照深度进栈

 

代码

 

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N=60010;
 6 struct edge{int to,from;}e[N*8];
 7 int n,m,L,R,cnt=1,ans=1,head[N],Q[N*2],q[N*2],f[N],Fa[N],deep[N],dfn[N],low[N];
 8 void insert(int x,int y)
 9 {
10     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt;
11     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt;
12 }
13 void dp(int x,int y)
14 {
15     int r=0;
16     for (int i=y;i!=x;i=Fa[i]) Q[++r]=i; Q[++r]=x;
17     reverse(&Q[1],&Q[r+1]);
18     for (int i=1;i<=r;i++) Q[i+r]=Q[i];
19     L=1,R=0;
20     for (int i=1;i<=r*2;i++)
21     {
22         while (L<=R&&i-q[L]>r/2) ++L;
23         if (L<=R) ans=max(ans,f[Q[i]]+f[Q[q[L]]]+i-q[L]);
24         while (L<=R&&f[Q[i]]-i>f[Q[q[R]]]-q[R]) R--;
25         q[++R]=i;
26     }
27     for (int i=y;i!=x;i=Fa[i]) f[x]=max(f[x],f[i]+min(deep[i]-deep[x],1+deep[y]-deep[i]));
28 }
29 void dfs(int x,int fa)
30 {
31     Fa[x]=fa,dfn[x]=low[x]=++dfn[0],deep[x]=deep[fa]+1;
32     for (int i=head[x];i;i=e[i].from) 
33     {
34         if (!dfn[e[i].to]) dfs(e[i].to,x),low[x]=min(low[x],low[e[i].to]); else if (e[i].to!=fa) low[x]=min(low[x],dfn[e[i].to]);
35         if (low[e[i].to]>dfn[x]) ans=max(ans,f[x]+f[e[i].to]+1),f[x]=max(f[x],f[e[i].to]+1);
36     }
37     for (int i=head[x];i;i=e[i].from) if (Fa[e[i].to]!=x&&dfn[x]<dfn[e[i].to]) dp(x,e[i].to);
38 }
39 int main()
40 {
41     scanf("%d%d",&n,&m);
42     for (int i=1,k,x,y;i<=m;i++)
43     {
44         scanf("%d%d",&k,&x);
45         for (int j=1;j<k;j++) scanf("%d",&y),insert(x,y),x=y;
46     }
47     dfs(1,0),printf("%d",ans);
48 }

 

上一篇:有向图的强连通分量(Tarjan)


下一篇:洛谷 题解 P3627 【[APIO2009]抢掠计划】