首页 > 代码库 > bzoj1023: [SHOI2008]cactus仙人掌图
bzoj1023: [SHOI2008]cactus仙人掌图
题解可以看这篇，写的很清楚……
http://z55250825.blog.163.com/blog/static/150230809201412793151890/
然后我的单调队列写出来竟然和他不一样……
max(f[i]+f[j]+j-i)j属于[i+1，i+sum/2]的话，对于j的话，不就是max(f[i]-i)+f[j]+j，维护f[i]-i递增不就行了么？
那么说一下这种环套树的基本写法……
首先是建图
然后跑tarjan，跑得时候要记录下某个点的父亲，然后如果某个点x的某个儿子son存在dfn[x]<low[too]，那么明显x-son就是一个桥……这一部分可以看成是树dp中某个节点和儿子。然后某个点跑完tarjan后再找出它所有fa[son]<>x且dfn[x]<dfn[too]，这时就是以x到too再到x的环，这时候就跑个循环dp，只不过要注意那个x取too就不能取，too取x就不能取，两遍for解决……
也就是树当树，环当环处理啦……
type arr=record toward,next:longint; end; const maxm=3000000; maxn=300000; var edge:array[0..maxm]of arr; first,num,a,f,p,dfn,low,dep,fa:array[0..maxn]of longint; n,m,time,tot,ans:longint; function max(x,y:longint):longint;begin if x<y then exit(y); exit(x);end; function min(x,y:longint):longint;begin if x<y then exit(x); exit(y);end; procedure addedge(i,j:longint);begin inc(tot); edge[tot].toward:=j; edge[tot].next:=first[i]; first[i]:=tot;end; procedure dp(x,root:longint);var sum,head,tail,i:longint;begin sum:=dep[x]-dep[root]+1; i:=x; while sum>0 do begin num[sum]:=f[x]; x:=fa[x]; dec(sum); end; x:=i; sum:=dep[x]-dep[root]+1; for i:=1 to sum do num[i+sum]:=num[i]; head:=1; tail:=1; p[1]:=1; for i:=2 to sum<<1 do begin while (head<=tail) and (p[head]+sum>>1<i) do inc(head); ans:=max(ans,num[p[head]]-p[head]+num[i]+i); while (head<=tail) and (num[p[tail]]-p[tail]<num[i]-i) do dec(tail); inc(tail); p[tail]:=i; end; for i:=2 to sum do f[root]:=max(f[root],min(i-1,sum-i+1)+num[i]);end; procedure tarjan(x:longint);var i,too:longint;begin inc(time); dfn[x]:=time; low[x]:=time; i:=first[x]; while i>0 do begin too:=edge[i].toward; if too<>fa[x] then begin if dfn[too]=0 then begin dep[too]:=dep[x]+1; fa[too]:=x; tarjan(too); if low[too]<low[x] then low[x]:=low[too]; end else if dfn[too]<low[x] then low[x]:=dfn[too]; if dfn[x]<low[too] then begin ans:=max(ans,f[x]+f[too]+1); f[x]:=max(f[x],f[too]+1); end; end; i:=edge[i].next; end; i:=first[x]; while i>0 do begin too:=edge[i].toward; if (fa[too]<>x) and (dfn[x]<dfn[too]) then dp(too,x); i:=edge[i].next; end;end; procedure into;var i,j,k:longint;begin readln(n,m); for i:=1 to m do begin read(k,a[1]); for j:=2 to k do begin read(a[j]); addedge(a[j],a[j-1]); addedge(a[j-1],a[j]); end; end;end; procedure work;begin time:=0; ans:=0; dep[1]:=1; tarjan(1); writeln(ans);end; begin into; work;end.
（有时间再搞搞丧心病狂的动态仙人掌）
bzoj1023: [SHOI2008]cactus仙人掌图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。