P2458 [SDOI2006] 保安站岗 题解

题目描述五一来临某地下超市为了便于疏通和指挥密集的人员和车辆以免造成超市内的混乱和拥挤准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状某些通道之间可以互相望见。总经理要求所有通道的每个端点树的顶点都要有人全天候看守在不同的通道端点安排保安所需的费用不同。一个保安一旦站在某个通道的其中一个端点那么他除了能看守住他所站的那个端点也能看到这个通道的另一个端点所以一个保安可能同时能看守住多个端点树的结点因此没有必要在每个通道的端点都安排保安。编程任务请你帮助超市经理策划安排在能看守全部通道端点的前提下使得花费的经费最少。输入格式第 1 行 n表示树中结点的数目。第 2 行至第 n1 行每行描述每个通道端点的信息依次为该结点标号 i0i≤n在该结点安置保安所需的经费 k1≤k≤10000该点的儿子数 m接下来 m 个数分别是这个节点的 m 个儿子的标号 r1​,r2​,⋯,rm​。对于一个 n0n≤1500个结点的树结点标号在 1 到 n 之间且标号不重复。输出格式输出一行一个整数表示最少的经费。输入输出样例输入 #1复制6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0输出 #1复制25说明/提示样例解释在结点 2,3,4 安置 3 个保安能看守所有的 6 个结点需要的经费最小25。思路:依旧树形DP。。状态dp[i][0]表示被父亲控制dp[i][1]表示被儿子控制dp[i][2]表示被自己控制。状态转移方程 dp[i][0]Σmin(dp[v][1],dp[v][0],dp[v][2]);dp[i][2]Σmin(dp[v][1],dp[v][0],dp[v][2]);dp[i][2]c[i];dp[i][1]要用反悔贪心。代码#include bits/stdc.h #include bits/cconfig.h #include ostream #include istream #include algorithm #include string.h #include stdlib.h #include stdio.h #include string #include math.h #include time.h #include ctime #include cstdlib #define ll long long #define ull unsigned long long #define db double #define st string #define ch char #define bo bool #define s1 27 #define s2 205 #define s3 2005 #define s4 20005 #define s5 200005 #define s6 2000005 #define s7 20000005 using namespace std; int n,dp[s3][3],s[s3]; vectorint g[s3]; void dfs(int u,int fa){ dp[u][2]s[u]; dp[u][0]0; int p1; int sum2141656782; for(int i0;ig[u].size();i){ int vg[u][i]; if(vfa) continue; dfs(v,u); dp[u][2]min({dp[v][0],dp[v][1],dp[v][2]}); dp[u][0]min(dp[v][1],dp[v][2]); if(dp[v][1]dp[v][2]){ p0; } summin(sum,dp[v][2]-dp[v][1]); dp[u][1]min(dp[v][1],dp[v][2]); } if(p){ dp[u][1]sum; } } int main(){ cinn; for(int i1;in;i){ int a,b,c; cinabc; s[a]b; for(int j1;jc;j){ int t; cint; g[t].push_back(a); g[a].push_back(t); } } dfs(1,0); coutmin(dp[1][1],dp[1][2]); return 0; }