P5766 [NOI1999] 最优联通子集 题解

include13_fAKe · 2023-08-23 11:37:05 · 题解

前言

以前的 NOI 真的如此简单吗？

题意

给定一颗树，点有点权，求树上连通块的最大权值（可以是连通块的一部分）。

为什么一定是树呢？

题中已经说到，整点集 V 是单整点集，即对于 V 中的任何两个整点， V 中有且仅有一条连接这两点的道路。

这不就是树的性质吗？

思路

树形 dp 模板题。

大多数的树形 dp 都是从叶向根更新、传值，这道题也不例外。

此题给出的是一棵无根树，但我们可以以 1 结点为根。

设 dp_u 表示在以 u 为根的子树中找到的包含 u 结点的所有连通块的最大权值。

对于所有 u 的子结点 v，如果 dp_v>0，就让 dp_u+=dp_v（不然 dp_u 反而变得更小了）。而 u 结点是必选的，所以不要忘了在 dp_u 中加上结点 u 本身的权值（C_u）。

定义函数

将转移方程式写成 \KaTeX 公式，就是这样的：

最终答案就是 \max dp_i 了。

接下来就可以认真做题了。

注意事项

• 由于 n \le 10^3，数据范围较小，所以可以通过枚举整点集 V 中每个点对是否相邻即可，无需对点集排序。n^2 的时间复杂度没有任何问题。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n;
int x[N],y[N],c[N];
bool vis[N];
int dp[N];
vector<int> g[N];
void dfs(int u){
    vis[u]=true;
    dp[u]=c[u];
//  cout<<u<<endl;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!vis[v]){
            dfs(v);
            if(dp[v]>0) dp[u]+=dp[v];
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                if(abs(x[i]-x[j])+abs(y[i]-y[j])==1){
                    g[i].push_back(j);
                }
            }
        }
    }
    dfs(1);
    int ans=INT_MIN;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]);
//      cout<<dp[i]<<endl;
    }
    cout<<ans<<endl;
    return 0;
}