$Recommend$
基环树学习笔记-$cly$_$none$:写得非常清晰漂亮。
$Find\;the\;Loop$
该代码可以找二元环。
$code\;by\;$$Gion$
1 | vector<int> G[MAXN]; //基环树 |
$Examples$
[ZJOI 2008]骑士
$Description$
基环树版「没有上司的舞会」。
$Solution$
给出两种做法。
问题要求求解的是一个基环树森林。但由于可能存在重边,森林中可能存在树,应该是要考虑进去的。
先以没有上司的舞会的方式处理环的子树($f[i][0/1]$),再处理环。
由于第一个点和最后一个点不能都选,所以在统计答案时要多加一维,表示1号点选不选。
$g[i][0/1][0/1]$表示环上的第i个点,1号点和i号点是否选择时,得到的最优答案。
再以没有上司的舞会的方式处理就可以了。
$Warning:$可以看出$g[2][1][1]$和$g[1][1][0]$之类是不存在的状态,因此要用到它的状态都要预处理好($g[1-3]$)。
dfs找出环上的任意两个点$u,v$,强行断开$(u,v)$。由于可能存在重边,要暴力特判。
以它们为根各做一次树形dp,答案取$max(f[u][0],f[v][0])$
两种做法的本质都是断边,但第二种实现较为容易。
给出第一种的$90pts$代码。
1 |
|