2013-11-17 08:52
原题传送门
N个骑士，每个人有一个仇人，那么，每个骑士只有一个后继，将他和他憎恨的人连边，就组成了
一颗内向树，内向树可以看成环儿上挂一堆树，那么我们对于每个环儿上的点，求出以该点为根节点
的子树，取不取该根节点的价值（树P就好了，类似于没有上司的舞会），然后我们得到了一个环儿
知道每个点取不取的价值，求最大价值，那么我们可以破环为链，固定第一个取不取，然后DP，如果
第一个取，那么答案就是c[tot,0]，不取的话答案就是max(c[tot,1],c[tot,0])，tot为环最后一个节点
然后取两个的最大值就好了，因为可能图有多个块，所以累加每个块的最大值就是ans。
Ps：我知道我的代码写的长。。。。风格。。。
//By BLADEVILvar n :int64; pre, last, other :array[0..1000010] of int64; l :int64; low, dfn, stack, key :array[0..1000010] of int64; flag :array[0..1000010] of boolean; time :int64; que :array[0..1000010] of int64; fuck :int64; tot :int64; v :array[0..1000010] of int64; w, c :array[0..1000010,0..2] of int64; finish :array[0..1000010] of boolean; ans :int64; function min(a,b:int64):int64;begin if a>b then min:=b else min:=a;end; function max(a,b:int64):int64;begin if a>b then max:=a else max:=b;end; procedure connect(x,y:int64);begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y;end; procedure init;var i :longint; y :int64;begin read(n); for i:=1 to n do begin read(v[i],y); connect(y,i); end;end; procedure dfs(x:int64);var p, q :int64; cur :int64;begin inc(time); dfn[x]:=time; low[x]:=time; inc(tot); stack[tot]:=x; flag[x]:=true; q:=last[x]; while q<>0 do begin p:=other[q]; if dfn[p]=0 then begin dfs(p); low[x]:=min(low[x],low[p]); end else if flag[p] then low[x]:=min(low[x],dfn[p]); q:=pre[q]; end; cur:=-1; if dfn[x]=low[x] then begin while cur<>x do begin cur:=stack[tot]; dec(tot); flag[cur]:=false; key[cur]:=x; end; end;end; procedure doit(x:int64);var q, p :int64; h, t :int64; cur :int64; i :longint; now :int64; begin t:=1; h:=0; que[1]:=x; q:=last[x]; while t<>h do begin inc(h); cur:=que[h]; q:=last[cur]; while q<>0 do begin p:=other[q]; if key[p]=fuck then begin q:=pre[q]; continue; end; inc(t); que[t]:=p; q:=pre[q]; end; end; for i:=t downto 1 do begin now:=que[i]; q:=last[now]; w[now,1]:=v[now]; if q=0 then w[now,1]:=v[now]; while q<>0 do begin p:=other[q]; if key[p]<>fuck then begin w[now,0]:=w[now,0]+max(w[p,0],w[p,1]); w[now,1]:=w[now,1]+w[p,0]; end; q:=pre[q]; end; end;end; procedure main;var i, j :longint; q, p :int64; f :boolean; now :int64; begin for i:=1 to n do if dfn[i]=0 then dfs(i); for i:=1 to n do if (low[i]<>dfn[i]) and (not finish[key[i]]) then begin fuck:=key[i]; finish[fuck]:=true; for j:=1 to n do if key[j]=fuck then doit(j); fillchar(flag,sizeof(flag),false); for j:=1 to n do if key[j]=fuck then break; fillchar(que,sizeof(que),0); que[1]:=j; tot:=1; f:=false; while true do begin q:=last[que[tot]]; while q<>0 do begin p:=other[q]; if flag[p] then begin f:=true; break; end; if key[p]=fuck then begin inc(tot); que[tot]:=p; flag[p]:=true; end; q:=pre[q]; end; if f then break; end; fillchar(c,sizeof(c),0); c[que[1],1]:=-maxlongint; c[que[1],0]:=w[que[1],0]; for j:=2 to tot-1 do begin c[que[j],0]:=max(c[que[j-1],0],c[que[j-1],1])+w[que[j],0]; c[que[j],1]:=c[que[j-1],0]+w[que[j],1]; end; now:=-maxlongint; for j:=2 to tot-1 do now:=max(now,max(c[que[j],0],c[que[j],1])); fillchar(c,sizeof(c),0); c[que[1],1]:=w[que[1],1]; c[que[1],0]:=-maxlongint; for j:=2 to tot-1 do begin c[que[j],0]:=max(c[que[j-1],0],c[que[j-1],1])+w[que[j],0]; c[que[j],1]:=c[que[j-1],0]+w[que[j],1]; end; for j:=2 to tot-2 do now:=max(now,max(c[que[j],0],c[que[j],1])); now:=max(now,c[que[tot-1],0]); inc(ans,now); end; writeln(ans);end; begin init; main;end.