Lukelabs OJ刷题——Z1013

发布时间:2023年12月26日

题意简述

题目背景

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

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

输入

输入第一行包含一个正整数 N N N,描述骑士团的人数;

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

输出

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

思路

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

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

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

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

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

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

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

注意以下几个坑点:

  • 要开 l o n g l o n g long long 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;
}

结语

今天的文章就到这里啦,三连必回哦!

文章来源:https://blog.csdn.net/yzc_qiuse/article/details/135174492
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。