题解 BZOJ 1023 [SHOI2008]cactus仙人掌图

题意是仙人掌图直径。
大概做法就是树的直径dp求法加上基环树的技巧特技。
改了好长好长时间啊。
参考题解: http://z55250825.blog.163.com/blog/static/150230809201412793151890/
很细致。。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int H[50005],X[20000005],P[20000005],tot=1;
int dp[50005];
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int stk[50005],top;
int dfn[50005];
int low[50005],tim;
int ans;
int list[100005],t;
struct N{
int pos,w;
N(int a=0,int b=0){
pos=a;w=b;
}
};
struct dddl{
N q[100005];
int h,t;
void clear(){
h=t=0;
}
void pop(int x){
if(q[h].pos==x) h++;
}
int ask(){
return q[h].w;
}
void push(N a){
while(h<t&&q[t-1].w<=a.w) t--;
q[t++]=a;
}
}q;
bool debug;
int fa[50005];
void dfs(int x){
dfn[x]=low[x]=++tim;
for(int i=H[x];i;i=X[i]){
if(P[i]==fa[x])continue;
if(fa[P[i]]&&dfn[P[i]]>dfn[x]){
//find circle
int k=P[i];
t=0;
while(k!=x) list[t++]=k,k=fa[k];
list[t++]=x;
int mx=0x80808080;
for(int j=0;j<t;j++){
list[j+t]=list[j];
mx=max(mx,dp[list[j]]+min(j+1,t-j-1));
}
q.clear();
q.push(N(0,dp[list[0]]));
int adds=0;
for(int j=1;j<2*t;j++){
q.pop(j-t/2-1);
adds++;
ans=max(ans,dp[list[j]]+adds+q.ask());
q.push(N(j,dp[list[j]]-adds));
}
dp[x]=max(dp[x],mx);
}else if(!low[P[i]]){
fa[P[i]]=x;
dfs(P[i]);
low[x]=min(low[x],low[P[i]]);
if(low[P[i]]>dfn[x])ans=max(ans,dp[x]+dp[P[i]]+1),dp[x]=max(dp[x],dp[P[i]]+1);
}else low[x]=min(low[x],dfn[P[i]]);
}
ans=max(ans,dp[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0,k;i<m;i++){
scanf("%d",&k);
int last;
scanf("%d",&last);
for(int i=1,t;i<k;i++){
scanf("%d",&t);
add(last,t);add(t,last);
last=t;
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框