【Luogu2458】保安站岗(动态规划)
规划 动态
2023-09-11 14:14:41 时间
【Luogu2458】保安站岗(动态规划)
题面
题目描述
五一来临,某地下超市为了便于疏通和指挥密集的人员和车辆,以免造成超市内的混乱和拥挤,准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状;某些通道之间可以互相望见。总经理要求所有通道的每个端点(树的顶点)都要有人全天候看守,在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点,那么他除了能看守住他所站的那个端点,也能看到这个通道的另一个端点,所以一个保安可能同时能看守住多个端点(树的结点),因此没有必要在每个通道的端点都安排保安。
编程任务:
请你帮助超市经理策划安排,在能看守全部通道端点的前提下,使得花费的经费最少。
输入输出格式
输入格式:
第1行 n,表示树中结点的数目。
第2行至第n+1行,每行描述每个通道端点的信息,依次为:该结点标号i(0<i<=n),在该结点安置保安所需的经费k(<=10000),该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。
对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。
输出格式:
最少的经费。
输入输出样例
输入样例#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\)分别被儿子/自己/父亲所控制时的最小代价
#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=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next;
}e[MAX<<1];
int h[MAX],cnt=1;
int W[MAX],n;
int f[MAX][3];
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][1]=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][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=f[u][0],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][0],f[v][1])+f[v][1]);
}
f[u][0]=ret;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
int bh=read();
W[bh]=read();
int m=read();
while(m--)
{
int v=read();
Add(bh,v);Add(v,bh);
}
}
dfs(1,0);
printf("%d\n",min(f[1][1],f[1][0]));
return 0;
}
相关文章
- 0/1背包问题(动态规划)
- 【CF1132F】Clear the String(动态规划)
- 【CF1082F】Speed Dial(动态规划)
- 【BZOJ5324】[JXOI2018]守卫(动态规划)
- 【BZOJ5298】[CQOI2018]交错序列(动态规划,矩阵快速幂)
- 【BZOJ1802】[AHOI2009]checker(动态规划)
- 【BZOJ2427】[HAOI2010]软件安装(动态规划,Tarjan)
- 【BZOJ4455】小星星(动态规划,容斥)
- 【BZOJ1063】【NOI2008】道路设计(动态规划)
- 【BZOJ1009】GT考试(KMP算法,矩阵快速幂,动态规划)
- 【Luogu1373】小a和uim之大逃离(动态规划)
- 【BZOJ1096】【ZJOI2007】仓库建设(斜率优化,动态规划)
- 【NOIP2016】换教室(动态规划)
- 【算法】【递归与动态规划模块】数组的最长子序列
- 第十六届全国大学生智能车竞赛赛题规划
- 【BZOJ2090/2089】[Poi2010]Monotonicity 2 动态规划+线段树
- 【BZOJ1700】[Usaco2007 Jan]Problem Solving 解题 动态规划
- LeetCode高频题62. 不同路径:机器人从左上角到右下角的路径有多少条?纯概率排列组合问题,而不是动态规划题
- [算法]死磕递归和动态规划专题算法
- POJ 3621 Sightseeing Cows (bellman-Ford + 01分数规划)
- leetcode 62. 不同路径-动态规划及优化,双100%
- 195、【动态规划】AcWing —— 91. 最短Hamilton路径(C++版本)
- 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
- 算法基础复盘笔记Day09【动态规划】—— 背包问题
- 在动态规划的海洋中遨游(二)
- 华为OD机试 - 高效的任务规划(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 24考研数学复习方法、全年规划
- poj 3390 Print Words in Lines 动态规划