0%

Project2458[SDOI2006]保安站岗项目报告

摘要:经典的树形$DP$

P2458 [SDOI2006]保安站岗

题面

题目分析

考虑树形$DP$.

设计状态$f_{i,0/1/2}$,表示$i$这个点由自己控制,由儿子控制或是由父亲控制的最小代价.

考虑转移,一个点如果被自己控制,那么儿子节点无论怎么选都可以,取儿子节点状态的最小值加上即可.

一个点如果被父亲控制,那么它的儿子不能是被父亲控制的状态,加上合法的状态即可.

一个点如果被儿子控制,那么它的儿子同样不能是被父亲控制的状态,但是需要注意的是,如果转移的时候它的儿子没有一个被自己控制,就需要选择一个被自己控制与被儿子控制的最优解差距最小的儿子节点来转移,以保证最优.

初始值为$f_{i,0}=w_{i}$.

目标值为$min( f_{1,0} , f_{1,1})$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "vector"

#define lxl long long
#define R register
#define INF 2147483647
#define debug(x) printf("debug:%lld\n",x)

using namespace std;

const lxl maxn=1510;

lxl n,ESize;
lxl head[maxn],w[maxn],dp[maxn][3],size[maxn];

struct _Edge
{
lxl next,to;
}e[maxn<<1];

inline lxl read(){char c=getchar();lxl f=1,output=0;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())output=(output<<1)+(output<<3)+c-'0';return output*f;}
inline void EdgeAdd(lxl from,lxl to){e[++ESize].next=head[from];e[ESize].to=to;head[from]=ESize;}
inline void dfs(lxl now,lxl from)
{
bool falg=false;
lxl MinDis=INF;
dp[now][0]=w[now];
for(R lxl i=head[now];~i;i=e[i].next)
{
lxl to=e[i].to;
if(to==from)continue;
dfs(to,now);
lxl GoodSon=min(dp[to][1],dp[to][0]);
dp[now][0]+=min(GoodSon,dp[to][2]);
dp[now][2]+=GoodSon;
if(dp[to][0]<dp[to][1])falg=true;
else MinDis=min(dp[to][0]-dp[to][1],MinDis);
dp[now][1]+=GoodSon;
}
if(!falg)dp[now][1]+=MinDis;
}

signed main(void)
{
memset(head,-1,sizeof(head));
n=read();
for(R lxl i=1;i<=n;++i)
{
lxl id=read();
w[id]=read();
size[id]=read();
for(R lxl j=1;j<=size[id];++j)
{
lxl a=read();
EdgeAdd(id,a);
EdgeAdd(a,id);
}
}
dfs(1,0);
printf("%lld\n",min(dp[1][0],dp[1][1]));
return 0;
}