讨论 / rq719 蒟蒻の题解
Hoblovski 2013-11-06 23:16:20
点我顶贴 收藏 删除
while rp+1>rp do rp:=rp+1;--From Hoblovski Den

题意:树的独立集(k<3)

又学到了 关于数据处理:

对于题目中这样的多叉树可以

1.转二叉树-->有的时候可以大幅改进效率(参见树状DP-选课的时间复杂度分析)

2.使用稀疏图的存法(前向星,邻接表)-->个人喜欢

题目有明显的最优子结构,可以使用动态规划.

然后题中给出的数据最开始很乱(无根树),缺乏拓扑序难以DP.

数据可达1e6,DFS爆栈,人工栈蛋疼.仔细想想,

这时不妨设1为根,跑一次BFS.

BFS给出的序列反过来就是拓扑序列,其深度递减.

再在这个拓扑序上跑DP就不用担心了

稍加思考可得,对于第一问状态表示只需要确定树根和树根是否选择.

并且第一问是最经典的树状DP之一,直接给方程

f[i,1]:以i为根的子树,取i时最大独立集的大小

f[i,0]:以i为根的子树,不取i时最大独立集的大小

f[i]=max(f[i,0],f[i,1])

f[i,0]=sigma(f[j])

f[i,1]=sigma(f[j,0])+1

其中j是i的儿子

时间O(V)*O(E/V) = O(E) = O(n)

对于第二问,明显也有最优子结构.

但是如果我们还沿用第一问的状态表示,方程很难想.

所以说不妨增加状态的表示,以求得方程.

题目中要求的是距离>2,所以想到了可以把

"i选不选"改为"i为根的子树中,所选择的距i最近的点距i的距离"

选自己则距离=0 选一个儿子不选自己则距离=1 etc

方程变为

f[i,j]:i为根的子树内,距i最近的选择点的距离为j时的最大独立集

再画图分析,考虑选择儿子孙子是的相互作用可得

f[i,0]=sigma(f[j,2])+1 //j是i的儿子,这种情况下没有冲突

f[i,1]=max(f[k,0]+f[j,1]) //k是i的某一个儿子,j是除k外的儿子,冲突存在于不能选择2个儿子

f[i,2]=sigma(f[j,1]) //j是i的儿子,无冲突

当然程序实现不必拘泥于此

这样第一问的方程可以改写.

时间O(kn)

NOIP2013

Rp:=5; Rp=Rp<<Rp;

while (1) { rp++; }

-其实我发这贴主要目的就是求RP--

渣码:

program rq719;

type pnode=^tnode;

tnode=record

n:longint;

next,opp,prev:pnode;

end;

-->用双向链表方便删除

var f:array[1..100000,-1..3] of longint;

g:array[1..100000] of pnode;

que:array[1..100000] of longint;

v:array[1..100000] of boolean;

n,k,top:longint;

function max(a,b:longint):longint; begin

if a>b then exit(a) else exit(b); end;

procedure init;

var tmp:pnode;

i,j,e1,e2:longint;

procedure ins(e1,e2:longint);

begin

new(tmp);

with tmp^ do begin

n:=e2;

next:=g[e1];

prev:=nil;

end;

if g[e1]<>nil then g[e1]^.prev:=tmp;

g[e1]:=tmp;

end;

begin

fillchar(g,sizeof(g),0);

fillchar(v,sizeof(v),0);

readln(n,k);

for i:=1 to n-1 do begin

readln(e1,e2);

ins(e1,e2);

ins(e2,e1);

g[e1]^.opp:=g[e2];

g[e2]^.opp:=g[e1];

end;

end;

procedure toposort;

var tmp:pnode;

down:longint;

begin

top:=n; down:=top; que[top]:=1;

while down>1 do begin

tmp:=g[que[top]];

dec(top);

while tmp<>nil do begin

if tmp^.opp^.prev<>nil then

tmp^.opp^.prev^.next:=tmp^.opp^.next

else g[tmp^.n]:=tmp^.opp^.next;

dec(down);

que[down]:=tmp^.n;

tmp:=tmp^.next;

end;

end;

end;

procedure work1;

var front,i,j,k,low,head:longint;

tmp:pnode;

begin

for front:=1 to n do begin

head:=que[front];

fillchar(f[head],sizeof(f[head]),0);

tmp:=g[head];

while tmp<>nil do begin

inc(f[head,0],f[tmp^.n,1]);

inc(f[head,1],f[tmp^.n,-1]);

tmp:=tmp^.next;

end;

inc(f[head,0]);

f[head,-1]:=max(f[head,0],f[head,1]);

end;

writeln(f[1,-1]);

end;

procedure work2;

var front,i,j,k,low,head,fact:longint;

tmp:pnode;

begin

for front:=1 to n do begin

head:=que[front];

fillchar(f[head],sizeof(f[head]),0);

tmp:=g[head];

fact:=0;

while tmp<>nil do begin

inc(f[head,0],f[tmp^.n,2]);

inc(f[head,1],f[tmp^.n,1]);

inc(f[head,2],f[tmp^.n,1]);

if f[tmp^.n,0]-f[tmp^.n,1]>fact then

fact:=f[tmp^.n,0]-f[tmp^.n,1];

tmp:=tmp^.next;

end;

inc(f[head,1],fact);

inc(f[head,0]);

end;

writeln(max(f[1,0],max(f[1,1],f[1,2])));

end;

begin

init;

toposort;

case k of

1:work1;

2:work2;

end;

end.

求NOIP2013 500+++++++

#1 Hoblovski@2013-11-06 23:16:49
回复 删除
哦不 我的缩进哪里去了
查看更多回复
提交回复