【Luogu2458】保安站崗（動态規劃）

題面

題目描述

五一來臨，某地下超市為了便于疏通和指揮密集的人員和車輛，以免造成超市内的混亂和擁擠，準備臨時從外機關調用部分保安來維持交通秩序。

已知整個地下超市的所有通道呈一棵樹的形狀；某些通道之間可以互相望見。總經理要求所有通道的每個端點（樹的頂點）都要有人全天候看守，在不同的通道端點安排保安所需的費用不同。

一個保安一旦站在某個通道的其中一個端點，那麼他除了能看守住他所站的那個端點，也能看到這個通道的另一個端點，是以一個保安可能同時能看守住多個端點（樹的結點），是以沒有必要在每個通道的端點都安排保安。

程式設計任務：

請你幫助超市經理策劃安排，在能看守全部通道端點的前提下，使得花費的經費最少。

輸入輸出格式

輸入格式：

第1行 n，表示樹中結點的數目。

第2行至第n+1行，每行描述每個通道端點的資訊，依次為：該結點标号i（0

輸入輸出樣例

輸入樣例#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

題解

題目大意是，給定一棵樹，每一個節點可以控制和他相鄰的節點，問最少用多少代價可以控制整棵樹

因為每個節點隻能夠控制相鄰的節點

是以設 f[i][0/1/2] 分别表示目前節點 i <script type="math/tex" id="MathJax-Element-19">i</script>分别被兒子/自己/父親所控制時的最小代價

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 1600
#define INF 1e9
inline int read()
{
    int x=,t=;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
    return x*t;
}
struct Line
{
    int v,next;
}e[MAX<<];
int h[MAX],cnt=;
int W[MAX],n;
int f[MAX][];
inline void Add(int u,int v)
{
    e[cnt]=(Line){v,h[u]};
    h[u]=cnt++;
}
void Plus(int &a,int b)
{
    a+=b;
    if(a>INF)a=INF;
}
void dfs(int u,int ff)
{
    f[u][]=W[u];
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==ff)continue;
        dfs(v,u);
        Plus(f[u][],min(f[v][],f[v][]));
        Plus(f[u][],min(f[v][],min(f[v][],f[v][])));
        Plus(f[u][],min(f[v][],f[v][]));
    }
    int tot=f[u][],ret=INF;
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==ff)continue;
        ret=min(ret,tot-min(f[v][],f[v][])+f[v][]);
    }
    f[u][]=ret;
}
int main()
{
    n=read();
    for(int i=;i<=n;++i)
    {
        int bh=read();
        W[bh]=read();
        int m=read();
        while(m--)
        {
            int v=read();
            Add(bh,v);Add(v,bh);
        }
    }
    dfs(,);
    printf("%d\n",min(f[][],f[][]));
    return ;
}