P2607

佬头 · 2023-11-15 23:28:44 · 题解

Description

为了讨伐邪恶国度，现准备有 n 个骑士，其中第 i 个骑士讨厌骑士 f_i~(f_i\ne i)，他是绝对不会与自己厌恶的人一同出征的。同时每名骑士有一个战斗力的估值 v_i，求最大化的所有出征骑士的战斗力总和。

Solution

由 i 向 f_i 建边，那么每个点就仅有一条出边，如果从一个点 i 不断沿着 f_i 走，总会陷入一个环中，因此不难想到它会是一棵内向基环树，整幅图就是一张内向基环森林。类似于：

内向基环树可以形象地理解为一个环上长了若干棵树，当然也存在某个没长树的环，那就把环和树分开来考虑（显然两种情况的限制是不一样的）：

• 树的话，不难想到是一个树形 dp，设 dp[i][1/0] 表示以 i 为根结点的子树 选/不选 i 时的最大战斗力，i 的儿子节点构成的集合为 S，则转移方程就是：

  \\&dp[f[i]][0]=\sum\limits_{j\in S}\max\left(dp[j][0],~dp[j][1]\right)\end{aligned}

  考虑如何把树和环分开来。就用拓扑排序吧，把环以外的结点全部先计算掉，同时把他们更新给根节点。

  到这里的话事实上与 P1352 没有上司的舞会 是一样的。

• 接下来就是环。显然它是首尾相接的，那么用原先的转移方程不可行（在环收尾的时候我们不知道起始节点是否被选在了最优方案里）。设 g[i][1/0][1/0] 表示当环查询到结点 i 时 选/不选 i 以及起始节点强制 选/不选 的最大战斗力，则转移方程就是：

  &g[f[i]][1][1]=dp[f[i]][1]+v[f[i]]+g[i][0][1] \\&g[f[i]][1][0]=dp[f[i]][1]+v[f[i]]+g[i][0][0] \\&g[f[i]][0][1]=dp[f[i]][0]+\max\left(g[i][0][1],~g[i][1][1]\right) \\&g[f[i]][0][0]=dp[f[i]][0]+\max\left(g[i][0][0],~g[i][1][0]\right) \end{aligned}

  设最后一个查询的点是 x，那么最终一棵基环树对答案的贡献就是 \max\left(g[x][1][0],g[x][0][1],g[x][0][0]\right)。

  但是这样在起始时好像会冲突嘞？如果起始节点强制选，那么它的下一个结点显然是绝对不能选的，同时对于起始节点 y，g[y][1][0],~g[y][0][1] 显然不实际。但事实上我只要在下一次转移的时候用 \max 把不现实的吃掉即可。

  我们只需要使 g[y][1][0]\le g[y][0][0],~g[y][0][1]\le g[y][0][0]，那么更优的 g[y][0][0] 一定会把另两种吃掉（限制更少，既满足 y 结点不选，又满足起始结点强制不选）

时间复杂度 \mathcal O(n)。

Code

在处理环的时候代码里的 g[i][1/0] 表示起始节点强制不选、dp[i][1/0] 表示起始节点强制选。

#include <iostream>
#define ll long long
using namespace std;
const int N = 1000006;
int n, f[N], out[N], q[N], back;
bool vis[N];
ll dp[N][2], g[N][2], ans;
int read(){
    int x = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return x;
}
void write(ll x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
int main(){
    n = read();
    for(int i = 1; i <= n; ++ i) dp[i][1] = read(), ++ out[f[i] = read()];
    for(int i = 1; i <= n; ++ i) if(!out[i]) q[++ back] = i;
    for(int front = 1; front <= back; ++ front){
        vis[q[front]] = 1;
        dp[f[q[front]]][0] += max(dp[q[front]][0], dp[q[front]][1]);
        dp[f[q[front]]][1] += dp[q[front]][0];
        if(!-- out[f[q[front]]]) q[++ back] = f[q[front]];
    }
    for(int i = 1, x; i <= n; ++ i)
        if(!vis[i]){
            g[i][0] = dp[i][0];
            for(x = i; f[x] != i; x = f[x]){
                vis[f[x]] = 1;
                g[f[x]][0] = dp[f[x]][0] + max(g[x][0], g[x][1]);
                g[f[x]][1] = dp[f[x]][1] + g[x][0];
                dp[f[x]][0] += max(dp[x][1], dp[x][0]);
                dp[f[x]][1] += dp[x][0];
            }
            ans += max(max(g[x][0], g[x][1]), dp[x][0]);
        }
    write(ans);
    return 0;
}

Weaken

P7752 [COCI2013-2014#2] PALETA

Similar

P1453 城市环路