【Luogu2458】保安站岗（动态规划）

题面

题目描述

五一来临&＃xff0c;某地下超市为了便于疏通和指挥密集的人员和车辆&＃xff0c;以免造成超市内的混乱和拥挤&＃xff0c;准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状&＃xff1b;某些通道之间可以互相望见。总经理要求所有通道的每个端点&＃xff08;树的顶点&＃xff09;都要有人全天候看守&＃xff0c;在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点&＃xff0c;那么他除了能看守住他所站的那个端点&＃xff0c;也能看到这个通道的另一个端点&＃xff0c;所以一个保安可能同时能看守住多个端点&＃xff08;树的结点&＃xff09;&＃xff0c;因此没有必要在每个通道的端点都安排保安。

编程任务&＃xff1a;

请你帮助超市经理策划安排&＃xff0c;在能看守全部通道端点的前提下&＃xff0c;使得花费的经费最少。

输入输出格式

输入格式&＃xff1a;

第1行 n&＃xff0c;表示树中结点的数目。

第2行至第n&＃43;1行&＃xff0c;每行描述每个通道端点的信息&＃xff0c;依次为&＃xff1a;该结点标号i&＃xff08;0

输入输出样例

输入样例#1&＃xff1a;

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&＃xff1a;

25

说明

样例说明&＃xff1a;在结点2&＃xff0c;3&＃xff0c;4安置3个保安能看守所有的6个结点&＃xff0c;需要的经费最小&＃xff1a;25

题解

题目大意是&＃xff0c;给定一棵树&＃xff0c;每一个节点可以控制和他相邻的节点&＃xff0c;问最少用多少代价可以控制整棵树

因为每个节点只能够控制相邻的节点
所以设f[i][0/1/2]分别表示当前节点i分别被儿子/自己/父亲所控制时的最小代价

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 1600
#define INF 1e9
inline int read()
{int x&＃61;0,t&＃61;1;char ch&＃61;getchar();while((ch<&＃39;0&＃39;||ch>&＃39;9&＃39;)&&ch!&＃61;&＃39;-&＃39;)ch&＃61;getchar();if(ch&＃61;&＃61;&＃39;-&＃39;)t&＃61;-1,ch&＃61;getchar();while(ch<&＃61;&＃39;9&＃39;&&ch>&＃61;&＃39;0&＃39;)x&＃61;x*10&＃43;ch-48,ch&＃61;getchar();return x*t;
}
struct Line
{int v,next;
}e[MAX<<1];
int h[MAX],cnt&＃61;1;
int W[MAX],n;
int f[MAX][3];
inline void Add(int u,int v)
{e[cnt]&＃61;(Line){v,h[u]};h[u]&＃61;cnt&＃43;&＃43;;
}
void Plus(int &a,int b)
{a&＃43;&＃61;b;if(a>INF)a&＃61;INF;
}
void dfs(int u,int ff)
{f[u][1]&＃61;W[u];for(int i&＃61;h[u];i;i&＃61;e[i].next){int v&＃61;e[i].v;if(v&＃61;&＃61;ff)continue;dfs(v,u);Plus(f[u][0],min(f[v][0],f[v][1]));Plus(f[u][1],min(f[v][0],min(f[v][1],f[v][2])));Plus(f[u][2],min(f[v][0],f[v][1]));}int tot&＃61;f[u][0],ret&＃61;INF;for(int i&＃61;h[u];i;i&＃61;e[i].next){int v&＃61;e[i].v;if(v&＃61;&＃61;ff)continue;ret&＃61;min(ret,tot-min(f[v][0],f[v][1])&＃43;f[v][1]);}f[u][0]&＃61;ret;
}
int main()
{n&＃61;read();for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){int bh&＃61;read();W[bh]&＃61;read();int m&＃61;read();while(m--){int v&＃61;read();Add(bh,v);Add(v,bh);}}dfs(1,0);printf("%d\n",min(f[1][1],f[1][0]));return 0;
}