题解：P11501 [ROIR 2019] 探险队 (Day 2)

· · 题解

前言：这道题 dp 做法找环的部分还没有用拓扑做的，补充一下。

这道题其实很像“上司的舞会”，就是求树上最大独立集。

这里我们把每个人向他讨厌的那个人连边（发现所有点出度均为 1，所以这是一个基环树）然后求树上相邻两个结点不能同时选择时，最多能选多少个点。

如果是在普通的树上，设 f[i][1/0] 表示结点 i 选或不选的最大价值，dp 即可。

基环树相当于套了一个环，考虑把环上的每一个点都当作根，跑一遍它们子树的最大点独立集（注意不能走到环上的点），然后再用“给一个环，相邻的两个元素不选，求选得的最大总和”的 dp 模板，对“基环”上的点再跑一遍 dp 把答案整合起来即可。

因为 DAG 图具有良好的 dp 结构，找环可以用拓扑排序，先把普通的点都 dp 了，拓扑结束后入度依然不为 0 的点就是环上的点。

一些实现细节见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 7;
const ll inf = 1e18;

int a[maxn], ind[maxn]; // ind记录入度
ll f[maxn][2]; // f[u][1/0]表示以选/不选u，其子树能得到的最大点独立集大小
bool vis[maxn]; // 记录每个点所在的连通块是否访问过

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] != -1){
            ind[a[i]] ++;
        }
    }

    queue<int> q;
    for(int i = 1; i <= n; i ++){
        if(ind[i] == 0){
            q.push(i);
        }
        f[i][1] = 1; // 初始化dp
    }

    ll ans = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        int v = a[u];
        if(v == -1){
            ans += max(f[u][0], f[u][1]); // 说明这个根节点不在环上，那么直接统计答案就好了
        }else{
            f[v][0] += max(f[u][0], f[u][1]); // 正常的树上最大独立集dp
            f[v][1] += f[u][0];
            ind[v] --;
            if(ind[v] == 0){
                q.push(v);
            }
        }
    }

    // 遍历剩下的入度不为0的结点（说明在环上）
    for(int i = 1; i <= n; i ++){
        if(ind[i] >= 1 && !vis[i]){
            vector<int> ring;
            ring.push_back(0); // 让下标从1开始
            int u = i;
            while(!vis[u]){ // 从一个点一直走，直到回到自己，就说明跑完了一整个环
                vis[u] = true;
                ring.push_back(u);
                u = a[u];
            }
            int len = ring.size() - 1;

            vector<vector<ll>> g(len + 1, {0, 0}); // g[i][1/0]表示结点i选/不选的最大答案（i在环上）
            // 首先钦定最后一个不选，则第一个选不选都行
            g[1][0] = f[ring[1]][0], g[1][1] = f[ring[1]][1];
            for(int j = 2; j <= len; j ++){
                g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];
                g[j][1] = g[j - 1][0] + f[ring[j]][1];
            }
            ll res1 = g[len][0];

            // 然后钦定第一个不选，则最后一个选不选都行
            g[1][0] = f[ring[1]][0], g[1][1] = -inf; // 初始化第一个选的收益为负无穷，相当于强制不选第一个
            for(int j = 2; j <= len; j ++){
                g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];
                g[j][1] = g[j - 1][0] + f[ring[j]][1];
            }
            ll res2 = max(g[len][0], g[len][1]);

            ans += max(res1, res2);
        }
    }

    cout << ans << '\n';
    return 0;
}