AcWing 1080. 骑士【树形DP】

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1080. 骑士【树形DP】原题链接中等

作者：

滑稽_ωﾉ , 2020-05-14 02:07:20 , 所有人可见 , 阅读 1310

11

2

题目描述

给定一个 $n$ 个点 $n$ 条边的没有自环的图，每个点有权值，
有边相连的两个点只能选其一，求可选方案的最大的点权之和。
$n \leq 10^6$

题意分析

题目中说每个人有一个最讨厌的人，这个人不愿与他最讨厌的人同时被选择。
看起来讨厌好像是单向的，但是稍微一想就会发现
如果 $a$ 讨厌 $b$，那么 $a$ 和 $b$ 不能同时选择，所以我们建一个无向图。

每个人最讨厌的人应该不会是自己（没有自环）
如果是一个 $n$ 个点 $n$ 条边的连通图的话，那么就是一棵基环树
~~众所周知~~基环树就是 $n$ 个点 $n$ 条边的连通图(有且仅有一个简单环)
但是讨厌的关系不保证连通，所以是很多个基环树233
我们对于每个基环树单独求最优解，加起来即可

基环树DP

时间复杂度 $O(n)$

如何找环

在建边的同时用并查集维护连通块，
如果打算建边的两个点已经连通，那么不建这条边，并把这两个点存起来

如何DP

像没有上司的舞会这道题一样，
定义 $f[u][0], f[u][1]$ 分别表示以 $u$ 为根的子树，不选 $u$ 或选 $u$ 号节点的最大价值

由于我们保存下来的点对之间没有建边，所以他们在同一棵树里，
我们只需要对这个树做简单的树形DP即可。
唯一的问题就是额外加了一个限制条件，保存下来的这个点对也不能同时选择。

设这两个点为 $a$，$b$
实际上我们分别以这两个点为根，求 $max(f[a][0], f[b][0])$ 即可
只要我们不选当前点，自然不会和另一个点冲突，至于另一个点选没选，那就是DP过程中的事了

注意我们对同一颗树DP两次，要记得重新初始化 $f[u][0], f[u][1]$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int n;
vector<PII> roots;
int w[N];
LL f[N][2];

LL dfs(int u, int fa)
{
    f[u][1] = w[u];
    f[u][0] = 0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs(j, u);
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
    return f[u][0];
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  p[i] = i;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d%d", &w[i], &x);

        int pa = find(i),  pb = find(x);
        if(pa != pb)
        {
            p[pa] = pb;
            add(i, x),  add(x, i);
        }
        else
            roots.push_back({x, i});
    }

    LL sum = 0;
    for(PII t : roots)
    {
        int a = t.x, b = t.y;
        LL res = dfs(a, -1);
        res = max(res, dfs(b, -1));
        sum += res;
    }
    printf("%lld", sum);
    return 0;
}

25 评论

理想主义者 12个月前

代码可以喔比大y老师的简洁

kimi123 2024-01-01 15:56

求助，为什么把dfs改成void然后下面取max{f[a][0],f[b][0]}会wa几个点啊

kimi123 2024-01-01 16:01

哦我会了

LittleMoMol 2022-08-09 09:10

dalao，为什么反向连边？是因为建的是有向边，方便树形DP吗？

WA_FOREVER 2022-12-08 00:53

如图，假如你找到环后断开1~4这条边，从1点开始树形DP，结果1点访问不到5点，就出错了，反向建边其实就是向每个点连边，就没有这种问题了。实在搞不明白就建双向边。

WineChord 2023-10-05 21:05

如果不是反向建边的话，形成的是内向树，做树形 DP 的时候你会发现有些点走不到

Coros_Trusds 2021-08-03 16:42

呜呜呜为这么这份代码洛谷AC；AW提交MLE？

求看

//2021/8/3

#include <cstdio>

#include <algorithm>

#define int long long

namespace sol
{
    inline int max(int x,int y)
    {
        return x>y?x:y;
    }

    inline int min(int x,int y)
    {
        return x<y?x:y;
    }

    inline int maxx(int x,int y,int z)
    {
        int ans=max(x,y);

        return max(ans,z);
    }
}

using namespace sol;

using namespace std;

const int ma=1000005;

struct Node
{
    int v;

    int nxt;
};

Node node[ma<<1];

int head[ma],fa[ma],a[ma];

bool vis[ma];

int dp[ma][5],tmp[ma][5]; 

int n,s,t;

int idx,cnt;

inline void add(int u,int v)
{
    node[++idx].v=v;

    node[idx].nxt=head[u];

    head[u]=idx;
}

inline int get(int x)
{
    if(fa[x]==x)
    {
        return x;
    }

    return fa[x]=get(fa[x]);
}

inline void merge(int x,int y)
{
    int f1=get(x);

    int f2=get(y);

    if(f1!=f2)
    {
        fa[f1]=f2;
    }
}

inline void dfs(int u,int fath)
{
    dp[u][1]=a[u];

    dp[u][0]=0;

    for(register int i=head[u];i;i=node[i].nxt)
    {
        int v=node[i].v;

        if(v!=fath)
        {
            dfs(v,u);

            dp[u][0]+=max(dp[v][0],dp[v][1]);

            dp[u][1]+=dp[v][0];
        }
    }
} 

inline int work(int x,int y)
{
    int ans1,ans2,ans3;

    swap(a[0],a[y]);

    dfs(x,0);

    ans1=dp[x][0],ans2=dp[x][1];

    swap(a[0],a[y]);

    swap(a[0],a[x]);

    dfs(y,0);

    ans3=dp[y][1];

    swap(a[x],a[0]);

    return maxx(ans1,ans2,ans3);
}

#undef int

int main(void)
{
    #define int long long

    scanf("%lld",&n);

    for(register int i=1;i<=n;i++)
    {
        fa[i]=i;
    }

    a[0]=-1e12;

    for(register int i=1;i<=n;i++)
    {
        int v;

        scanf("%lld%lld",&a[i],&v);

        if(get(i)==get(v))
        {
            tmp[++cnt][0]=i;

            tmp[cnt][1]=v;
        }

        else
        {
            add(i,v);

            add(v,i);

            merge(i,v); 
        }
    }

    int ans=0;

    for(register int i=1;i<=cnt;i++)
    {
        ans+=work(tmp[i][0],tmp[i][1]);
    }

    printf("%lld\n",ans);

    return 0;
}