首页 > 代码库 > 【距离GDKOI:44天&GDOI:107天】【BZOJ1040】[ZJOI2008] 骑士

【距离GDKOI:44天&GDOI:107天】【BZOJ1040】[ZJOI2008] 骑士

    其实已经准备退役了,但GDOI之前还是会继续学下去的!!当成兴趣在学,已经对竞赛失去信心了的样子,我还是回去跪跪文化课吧QAQ

    第一道环套树DP...其实思想挺简单的,就把环拆开,分类处理。若拆成开的两个点是u,v,dp[i,0..1]分别表示第i位骑士不选和选

    (1) 不选u,v点随意    (2)u随意,v点不选...

    分类dp处理即可

  1 const maxn=1000419;  2 type  3  edgetype=record  4   toward,next:longint;  5  end;  6   7 var  8  edge:array[0..maxn*2] of edgetype;  9  first:array[0..maxn] of longint; 10  val:array[0..maxn] of int64; 11  dp:array[0..maxn,0..1] of int64; 12  pd,vb,vc:array[0..maxn] of boolean; 13  root,vv,e,tot:longint; 14  n:longint; 15 function max(x,y:int64):int64; begin if x>y then exit(x) else exit(y); end; 16  17 procedure addedge(i,j:longint); 18 begin 19  edge[tot].toward:=j; 20  edge[tot].next:=first[i]; 21  first[i]:=tot; 22  inc(tot); 23 end; 24  25 procedure add(i,j:longint); 26 begin 27  addedge(i,j); addedge(j,i); 28 end; 29  30 procedure dfs(v,fa:longint); 31 var i,tmp:longint; 32 begin 33  pd[v]:=true; 34  i:=first[v]; 35  while i<>-1 do 36   begin 37    tmp:=edge[i].toward; 38    if not pd[tmp] then dfs(tmp,v) 39     else if tmp<>fa then 40      begin 41       vv:=v; 42       root:=tmp; 43       e:=i; 44      end; 45    i:=edge[i].next; 46   end; 47 end; 48  49 procedure dpb(v:longint); //ban u 50 var i,tmp:longint; 51 begin 52  dp[v,0]:=0; dp[v,1]:=val[v]; vb[v]:=true; 53  i:=first[v]; 54  while i<>-1 do 55   begin 56    tmp:=edge[i].toward; 57    if (i<>e) and (i xor 1<>e) and not vb[tmp] then 58     begin 59      dpb(tmp); 60      dp[v,0]:=dp[v,0]+max(dp[tmp,0],dp[tmp,1]); 61      dp[v,1]:=dp[v,1]+dp[tmp,0]; 62     end; 63    i:=edge[i].next; 64   end; 65 end; 66  67 procedure dpc(v:longint); //ban v; 68 var i,tmp:longint; 69 begin 70  dp[v,0]:=0; dp[v,1]:=val[v]; vc[v]:=true; 71  i:=first[v]; 72  while i<>-1 do 73   begin 74    tmp:=edge[i].toward; 75    if (i<>e) and (i xor 1 <>e) and not vc[tmp] then 76     begin 77      dpc(tmp); 78      dp[v,1]:=dp[v,1]+dp[tmp,0]; 79      if tmp=vv then dp[v,0]:=dp[v,0]+dp[tmp,0] 80       else dp[v,0]:=dp[v,0]+max(dp[tmp,0],dp[tmp,1]); 81     end; 82    i:=edge[i].next; 83   end; 84 end; 85  86 procedure solve; 87 var i:longint; 88  rec,ans:int64; 89 begin 90  ans:=0; 91  for i:= 1 to n do 92   if not pd[i] then 93    begin 94     rec:=0; root:=-1; dfs(i,-1); 95     dpb(root); rec:=dp[root,0]; 96     dpc(root); rec:=max(rec,max(dp[root,0],dp[root,1])); 97     inc(ans,rec); 98    end; 99  writeln(ans);100 end;101 102 procedure init;103 var i,x:longint;104 begin105  fillchar(first,sizeof(first),255);106  readln(n);107  tot:=0;108  for i:= 1 to n do109   begin110    readln(val[i],x);111    add(i,x);112   end;113 end;114 115 Begin116  init;117  solve;118 End.

 

【距离GDKOI:44天&GDOI:107天】【BZOJ1040】[ZJOI2008] 骑士