皇宫看守

LOJ

题意:太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫.皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状，某些宫殿间可以互相望见.大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同.可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫.帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少.

分析:对于一个树上的节点,它能被守卫,只有三种情况.设\(f[i][0],f[i][1],f[i][2]\)分别表示节点i能被父亲节点,儿子节点,自己看到的情况下,以i为根的树的最小花费.

\(f[i][0]=\sum min(f[j][1],f[j][2])\),j是i的儿子.很好理解,i能被父节点看到,那么i的儿子j 要么被它自己的子节点看到,要么被自己看到.

\(f[i][1]=\sum min(f[j][1],f[j][2])+d\).i能被子节点看到,那么i的子节点j 要么被它自己的子节点看到,要么被自己看到.但与上一种情况不同的是,至少有一个j必须要被自己看到,这才能保证i被子节点看到.所以要加上d,\(d=min(f[j][2]-min(f[j][1],f[j][2]))\).解释一下,里层的min如果取了\(f[j][1]\)说明i的所有子节点j都是被子节点看到,这时我们强制让一个点被自己看到,即加上\(f[j][2]-f[j][1]\);而如果里层的min取的是\(f[j][2]\),那么就加上\(d=0\)不改变结果.

\(f[i][3]=\sum min(f[j][0],f[j][1],f[j][2])+val[i]\).如果i能被自己看到,即在i放置一个守卫,则i的子节点j三种情况都可能存在,别忘了加上在i放置守卫的花费\(val[i]\)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=1505;
int val[N],bj[N],f[N][3];
int tot,head[N],nxt[N],to[N];
inline void add(int x,int y){nxt[++tot]=head[x];head[x]=tot;to[tot]=y;}
inline void DP(int x,int fa){
    int d=1e9;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa)continue;
        DP(y,x);
        f[x][0]+=min(f[y][1],f[y][2]);
        f[x][1]+=min(f[y][1],f[y][2]);
        f[x][2]+=min(f[y][0],min(f[y][1],f[y][2]));
        d=min(d,f[y][2]-min(f[y][2],f[y][1]));
    }
    f[x][1]+=d;f[x][2]+=val[x];
}
int main(){
    int n=read();
    for(int i=1,x,num;i<=n;i++){
        x=read();val[x]=read();num=read();
        for(int j=1,y;j<=num;j++){
            y=read();add(x,y);bj[y]=1;
        }
    }
    int root=1;while(bj[root])root++;
    DP(root,0);
    printf("%d\n",min(f[root][1],f[root][2]));
    return 0;
}

皇宫看守

原文：https://www.cnblogs.com/PPXppx/p/11004183.html