Lukelabs OJ刷题——Z1013

题意简述

题目背景

有一个骑士团，共有$N$名骑士，每个骑士都有一个武力值和一个最讨厌的骑士（不是他自己），他无法和自己最讨厌的骑士战斗。

现在请你求出骑士团上场时的武力最大值。

输入

输入第一行包含一个正整数 $N$，描述骑士团的人数；

接下来 $N$ 行每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出

输出包含一行，一个整数，表示你所选出的骑士军团的战斗力。

思路

这题是一个很裸的树形DP，但是坑点很多。

思路：我们把一个骑士和他憎恨的骑士连边，很显然这会构成一个由基环树组成的森林。

我们对这个基环树森林进行树形DP（类似于没有上司的舞会），对于每一棵基环树，任意相连的两个点不能同时取。

众所周知，要使一棵基环树转化为一棵树，必须要断掉其环上的一条边。

我们考虑环上的任意一条边，它的两个端点至少有一个不取。则分别以两个端点为根进行树形DP，分别存在$f$数组和$g$数组中。

$dp[i][j]$的第一维表示以$i$为根节点的子树中，当前节点$i$取或不取的武力最大值($j$为$0$时表示不取，为$1$时表示取)。

我们可以发现，对于每一条环上的边，它的贡献相同，令任意边两端点分别为$x1,x2$，则对每个基环树（联通块）将答案累加上$max(f[x1][0],g[x2][0])$即可

注意以下几个坑点：

• 要开$longlong$
• 组成的是基环树森林而非单棵基环树
• 判断不走断开的边时必须用边来判断，不能用点，因为两个骑士可能相互憎恨，形成重边，这时如果判断点，会造成树不联通。

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PII pair<int, int>
#define For(i, a, b) for(int i = a;i <= b;i++)
const int N = 1e6 + 10;
int happy[N];
long long f[N][2];
struct node{
    int next, to, v;
} e[2 * N - 10];
int st[N], n, s, tot, x1, x2, E, b;
bool vis[N];
void add(int x, int y){
    e[tot].to = y, e[tot].next = st[x], st[x] = tot++;
    e[tot].to = x, e[tot].next = st[y], st[y] = tot++;
}
void find_circle(int x, int pre){
    vis[x] = true;
    for (int i = st[x]; ~i; i = e[i].next){
        if ((i ^ 1) == pre){
            continue;
        }
        if (vis[e[i].to]){
            x1 = x, x2 = e[i].to;
            E = i;
            continue;
        }
        find_circle(e[i].to, i);
    }
}
void dfs(int x, int pre){
    f[x][0] = 0;
    f[x][1] = happy[x];
    for (int i = st[x]; ~i; i = e[i].next){
        if ((i ^ 1) == pre){
            continue;
        }
        if (i == E || (i ^ 1) == E){
            continue;
        }
        dfs(e[i].to, i);
        f[x][1] += f[e[i].to][0];
        f[x][0] += max(f[e[i].to][1], f[e[i].to][0]);
    }
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    For (i, 1, n){
        st[i] = -1;
    }
    for (int i = 1; i <= n; i++){
        cin >> happy[i] >> b;
        add(i, b);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++){
        if (vis[i]){
            continue;
        }
        find_circle(i, -2);
        dfs(x1, -1);
        long long temp = f[x1][0];
        dfs(x2, -1);
        temp = max(temp, f[x2][0]);
        ans += temp;
    }
    cout << ans;
}

结语

今天的文章就到这里啦，三连必回哦！