BZOJ1040 骑士

题解

一类基环树题目的套路
首先发现可以将题目中的痛恨关系转化成一些基环树(显然是无向边)
首先考虑如果是树应该怎么做,就是一个及其简单的树形 $dp$
设状态 $f[i][0/1]$ 表示节点 $i$ 选或不选的最大战斗力总和
于是有转移
$$ f[i][1]=\sum f[son[i]][0] $$
$$ f[i][0]=\sum max{f[son[i]][0], f[son[i]][1]} $$

然后考虑对于环的情况应该怎么做
然后对于每个基环树,找到环上任意两个点 $S,T$ ,将两点之间的边拆开,此时这颗基环树变成了一颗树
由 $S$ 为根再由 $T$ 为根分别做两次 $dp$
取其中的最大值就是答案
需要注意的是有多个环

代码

#define MAX_N 2000007

int N, S, T;
int h[MAX_N];
int head[MAX_N], to[MAX_N * 2], nxt[MAX_N * 2], cap = 1;
ll val[MAX_N], f[MAX_N][2];
bool vis[MAX_N], del[MAX_N * 2];

inline void addEdge (int u, int v) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
}

inline void input () {
    read(N);
    int u;
    for (int i = 1; i <= N; ++i) {
        read(val[i]);
        read(u);
        h[i] = u;
        addEdge(u, i);
        addEdge(i, u);
    }
}

void find (int x, int fa) {
    vis[x] = true;
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa) {
            if (vis[to[i]]) {
                S = x, T = to[i];
                del[i] = del[i ^ 1] = true;
            } else {
                find(to[i], x);
            }
        }
}

void dfs (int x, int fa) {
    f[x][1] = val[x], f[x][0] = 0;
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa && !del[i]) {
            dfs(to[i], x);
            f[x][1] += f[to[i]][0];
            f[x][0] += std::max(f[to[i]][0], f[to[i]][1]);
        }
}

inline void solve () {
    ll res = 0, ans = 0;
    for (int i = 1; i <= N; ++i)
        if (!vis[i]) {
            find(i, 0);
            dfs(S, 0);
            ans = f[S][0];
            dfs(T, 0);
            ans = std::max(ans, f[T][0]);
            res += ans;
        }
    printf("%lld\n", res);
}

int main () {
    input();
    solve();
    return 0;
}

引用资料

FYT 讲课资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注