To boldly go where no one has gone before.

【学习笔记】基环树dp

2019-05-17 17:22:33


例题 P2515

分析这道题,每个软件$i$依赖于$d[i]$,那么就可以从$d[i]$向$i$连一条边,表示只有装了$d[i]$后,装$i$才有意义。由于每个软件最多依赖一个不为自己的软件,因此,每个点的入度最大为$1$,给定的软件就构成了一片基环外向树森林。比如,其中一棵树可能长这样:

1.th.jpg

就非常形象了。

那么考虑怎么对环处理,由于题意,对于环上的软件,只有在所有处在同一个环上的软件都被安装后,才能够产生价值,因此可以先用$\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}$


完整代码

#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

这道题就是另一种基环树的题目了。由题目知每个点出度为$1$,不难推理出连通块中最多只存在一个环。因此可以枚举环边 $<u,v>$ 进行断边,此后整个连通块形成一棵树,就可以分别以$u$和$v$为根跑一次树形$\text{dp}$,即得到这个连通块的所有信息。

处理连通块的时候,可以采用并查集维护连通性,如果输入的边所连接的两点$u,v$已经处于一个连通块当中,那么这个边就是可以被去掉的环边,就可以将其保存下来。此后,对于所有环边依次进行断边,然后对两个端点跑$\text{dp}$,如此处理之后即可得到答案。

#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

这道题就更简单了,保证图中只有一个环,那么就可以直接找断边,然后跑两次树形$\text{dp}$就搞定了。注意点序起始是0还是1,现场被坑。

#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;
}