P2458 [SDOI2006] 保安站岗 https://www.luogu.org/problemnew/show/P2458
最终决定重新打一遍这题 然后被儿子覆盖的这个情况还是重新看一遍以前的代码才捋清楚 QAQ
每个点有三种状态 自己覆盖自己 被父亲覆盖 被儿子覆盖
然后要注意被儿子覆盖时的转移 最后如果都是儿子被孙子覆盖的花费更少的话 得选一个儿子自己覆盖自己花费最少的来覆盖
最后输出根节点中自己覆盖自己和被儿子覆盖中较小的一个
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- #include<cmath>
- #include<stack>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define rg register
- const int N=1500+5,inf=0x3f3f3f3f;
- int n,a[N],ns,s,f[N][3];
- template <class t>void rd(t &x)
- {
- x=0;int w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- x=w?-x:x;
- }
- int head[N],tot=0;
- struct edge{int v,nxt,w;}e[N<<1];
- void add(int u,int v)
- {
- e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;
- }
- void dp(int u,int fa)
- {
- f[u][0]=a[u],f[u][1]=f[u][2]=0;
- bool yes=0;int minc=inf;
- for(int i=head[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==fa) continue;
- dp(v,u);
- f[u][0]+=min(f[v][1],min(f[v][0],f[v][2]));// 自己覆盖自己
- f[u][1]+=min(f[v][0],f[v][2]);// 被父亲覆盖
- f[u][2]+=min(f[v][0],f[v][2]) ;// 被儿子覆盖
- if(f[v][0]<=f[v][2]) yes=1;
- else minc=min(minc,f[v][0]-f[v][2]);
- }
- if(!yes) f[u][2]+=minc;
- }
- int main()
- {
- //freopen("in.txt","r",stdin);
- //freopen("nocows.out","w",stdout);
- rd(n);
- for(rg int i=1;i<=n;++i)
- {
- rd(i),rd(a[i]),rd(ns);
- for(rg int j=1;j<=ns;++j) rd(s),add(i,s),add(s,i);
- }
- dp(1,0);
- printf("%d",min(f[1][0],f[1][2]));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3054672.html