【学习笔记】基环树dp
NCC79601
2019-05-17 17:22:33
## 例题 [P2515](https://www.luogu.org/problemnew/show/P2515)
分析这道题，每个软件$i$依赖于$d[i]$，那么就可以从$d[i]$向$i$连一条边，表示只有装了$d[i]$后，装$i$才有意义。由于每个软件最多依赖一个不为自己的软件，因此，每个点的入度最大为$1$，给定的软件就构成了一片**基环外向树森林**。比如，其中一棵树可能长这样：
[](https://img.ffis.me/image/DtbF)
就非常形象了。
那么考虑怎么对环处理，由于题意，对于环上的软件，只有在所有处在同一个环上的软件都被安装后，才能够产生价值，因此可以先用$\textbf{Tarjan}$**缩点**，这样就转化成没有环的森林了。
接下来要对森林进行$\text{dp}$，因为所有树上的软件都可能对最终答案造成影响，然而一棵树与另一棵树又保持相对独立，所以不能直接用$\text{toposort}$处理（之前就因为直接$\text{toposort}$丢了40分…）。
考虑把$0$作为**超级根**（虚点），每棵树上任意入度为$0$的点作为根，从$0$开始向所有树考虑，然后把结果汇集于$0$，这样就可以在$0$处获得答案。
具体做法为：维护$f[u][i]$，表示考虑以$u$为根节点的子树，当最大容量为$i$时的最大价值，易得转移方程为：
$$f[u][i+w[u]]=\max f[u][i+w[u]-j]+f[v][j]$$
**注意**：转移方程中，$i$应**倒序**枚举，因为答案无前效性；$j$应**顺序**枚举，因为需要让$f[u][w[u]-j]$是倒序枚举。
最后，$f[0][m]$即是答案。
链接：[有向无环图$\text{dp}$](https://ncc79601.blog.luogu.org/DAG-dp)
---
完整代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const int MAXM = 510;
int n, m;
int w[MAXN], V[MAXN], d[MAXN], _w[MAXN], _V[MAXN], _d[MAXN];
vector<int> to[MAXN], _to[MAXN];
int dfn[MAXN], low[MAXN], clr[MAXN], color = 0, s[MAXN], top = 0;
bool ins[MAXN];
int indeg[MAXN], f[MAXN][MAXM];
void tarjan(int u)
{
static int dfn_cnt = 0;
dfn[u] = low[u] = ++dfn_cnt;
s[++top] = u;
ins[u] = true;
for(int i = 0; i < to[u].size(); i++)
{
int v = to[u][i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else
if(ins[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u])
{
color++;
int v;
while(v = s[top--])
{
ins[v] = false;
clr[v] = color;
_V[color] += V[v];
_w[color] += w[v];
if(v == u)
break;
}
}
return;
}
void dp(int u)
{
for(int i = _w[u]; i <= m; i++)
f[u][i] = _V[u];
for(int k = 0; k < _to[u].size(); k++)
{
int v = _to[u][k];
dp(v);
for(int i = m - _w[u]; i >= 0; i--)
for(int j = 0; j <= i; j++)
f[u][i + _w[u]] = max(f[u][i + _w[u]], f[u][i + _w[u] - j] + f[v][j]);
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for(int i = 1; i <= n; i++)
scanf("%d", &V[i]);
for(int i = 1; i <= n; i++)
{
scanf("%d", &d[i]);
if(d[i])
to[d[i]].push_back(i);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
tarjan(i);
for(int i = 1; i <= n; i++)
{
if(clr[i] != clr[d[i]])
{
_to[clr[d[i]]].push_back(clr[i]);
indeg[clr[i]]++;
}
}
for(int i = 1; i <= n; i++)
if(!indeg[i])
_to[0].push_back(i);
dp(0);
printf("%d", f[0][m]);
return 0;
}
```
## 例题 [P2607](https://www.luogu.org/problemnew/show/P2607)
这道题就是另一种基环树的题目了。由题目知每个点出度为$1$，不难推理出连通块中最多只存在一个环。因此可以枚举环边 $<u,v>$ 进行断边，此后整个连通块形成一棵树，就可以分别以$u$和$v$为根跑一次树形$\text{dp}$，即得到这个连通块的所有信息。
处理连通块的时候，可以采用**并查集**维护连通性，如果输入的边所连接的两点$u,v$已经处于一个连通块当中，那么这个边就是可以被去掉的**环边**，就可以将其保存下来。此后，对于所有环边依次进行断边，然后对两个端点跑$\text{dp}$，如此处理之后即可得到答案。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int fa[MAXN], n, power[MAXN];
long long f[MAXN][2];
struct EDGE
{
int to, next;
} edge[MAXN * 2];
int last[MAXN], id = 0;
int P1[MAXN], P2[MAXN], E[MAXN], cnt = 0;
bool cut[MAXN];
void build_edge(int u, int v)
{
edge[++id].to = v;
edge[id].next = last[u];
last[u] = id;
return ;
}
int getfa(int x)
{
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void merge(int x, int y)
{
if(getfa(x) == getfa(y))
return ;
fa[getfa(y)] = getfa(x);
return ;
}
void dfs(int u, int father)
{
f[u][0] = 0, f[u][1] = power[u];
for(int i = last[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if(v == father || cut[i])
continue;
dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
return ;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= n; i++)
{
int hate;
scanf("%d%d", &power[i], &hate);
build_edge(i, hate);
build_edge(hate, i);
if (getfa(i) == getfa(hate))
{
P1[++cnt] = i;
P2[cnt] = hate;
E[cnt] = id - 1;
// 存断边
}
else
merge(i, hate);
}
long long ans = 0;
for (int i = 1; i <= cnt; i++)
{
cut[E[i]] = cut[E[i] + 1] = true;
// 切边
dfs(P1[i], 0);
long long f1 = f[P1[i]][0];
dfs(P2[i], 0);
long long f2 = f[P2[i]][0];
ans += max(f1, f2);
cut[E[i]] = cut[E[i] + 1] = false;
}
printf("%lli", ans);
return 0;
}
```
---
## 另一道例题 [P1453](https://www.luogu.org/problemnew/show/P1453)
这道题就更简单了，保证图中只有一个环，那么就可以直接找断边，然后跑两次树形$\text{dp}$就搞定了。**注意点序起始是0还是1**，现场被坑。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, p[MAXN], fa[MAXN], f[MAXN][2], ans = 0;
double k;
int P1, P2, cut;
struct EDGE
{
int to, next;
} edge[MAXN * 2];
int head[MAXN], id = 0;
int getfa(int x)
{
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void merge(int x, int y)
{
if(getfa(x) == getfa(y))
return;
fa[getfa(y)] = getfa(x);
return ;
}
void build_edge(int u, int v)
{
edge[++id].to = v;
edge[id].next = head[u];
head[u] = id;
return ;
}
void dfs(int u, int father)
{
f[u][0] = 0, f[u][1] = p[u];
for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if((v == father) || ((i == cut) || (i - 1 == cut)))
continue;
dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
return;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &p[i]);
fa[i] = i;
}
for (int i = 1; i <= n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
build_edge(u, v);
build_edge(v, u);
if(getfa(u) == getfa(v))
{
P1 = u, P2 = v;
cut = id - 1;
}
else
{
merge(u, v);
}
}
scanf("%lf", &k);
dfs(P1, -1);
ans = f[P1][0];
dfs(P2, -1);
ans = max(ans, f[P2][0]);
printf("%.1lf", ans * k);
return 0;
}
```