当前位置: 首页 > news >正文

消防局的设立

消防局的设立

问题描述

由题意知,及给定一颗树,若节点内建立消防站,周围两个内均不需要建立消防站,问至少需要多少个消防站才能让整个树不发生不可控的火灾?

思路

·f[x][0]:至少让x向上2层之下都覆盖信号的答案。
·f[x][1]:至少让x向上1层之下都覆盖信号的答案。
·f[x][2]:至少让x自己及之下覆盖信号的答案。
·f[x][3]:至少让x向下1层之下都覆盖信号的答案。
·f[x][4]:至少让x向下2层之下都覆盖信号的答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=INT_MAX;
int n,f[1010][5];
vector<int> G[1010];
void dfs(int x) {if(G[x].empty()) {f[x][0]=1,f[x][1]=1,f[x][2]=1;return;}for(int i:G[x]) dfs(i);f[x][0]=1;int mi=N,mn=N;for(int i:G[x]){f[x][0]+=f[i][4];f[x][1]+=f[i][3];f[x][2]+=f[i][2];f[x][3]+=f[i][2];f[x][4]+=f[i][3];mi=min(mi,f[i][0]-f[i][3]);mn=min(mn,f[i][1]-f[i][2]);}f[x][1]+=mi;f[x][2]+=mn;f[x][1]=min(f[x][1],f[x][0]);f[x][2]=min(f[x][2],f[x][1]);f[x][3]=min(f[x][3],f[x][2]);f[x][4]=min(f[x][4],f[x][3]);
}
int main() {cin>>n;for(int i=2; i<=n; i++) {int u;cin>>u;G[u].emplace_back(i);}dfs(1);cout<<f[1][2];
}
http://www.hskmm.com/?act=detail&tid=34456

相关文章:

  • Python 潮流周刊#73:让我们对 PyPI 温柔一点,好吗?
  • 2025 年中国超声波流量计行业品牌全景分析报告:十大高性能品牌技术、性能与市场优势深度解析
  • 2025年精密弹簧厂家推荐排行榜,微型精密弹簧,不锈钢精密弹簧,高弹性精密弹簧公司推荐!
  • 2025网络推广服务推荐:云数智推,专业定制化营销解决方案!
  • React+Three.js 实现 Apple 2025 热成像 logo
  • 详细介绍:遥感目标检测数据集汇总,覆盖城市问题/工业安全/农业健康/室内场景……
  • 数据采集与融合作业1
  • CSP-S2023题解
  • 2025年氧化镁厂家最新推荐排行榜,活性氧化镁,肥料级氧化镁,优质供应与技术实力之选!
  • 运算符与自增自减
  • 2025年通风天窗/排烟天窗/通风气楼厂家最新推荐榜单,屋顶通风器/顺坡气楼/10A/1型/TC5A/TC12B/屋脊通风天窗公司推荐!
  • 使用autoDL gpu云服务器训练yolo的常用操作 - 东南西北风
  • 软件工程第三次作业-结对项目
  • with关键字
  • 2025精密球轴承优质厂家推荐:无锡雨露精工,国产高端定制首选!
  • 自定义注解
  • 2025 年电磁流量计最新推荐榜,聚焦企业技术实力与市场口碑深度解析
  • 2025 年涡轮流量计厂家企业品牌推荐排行榜,揭秘行业前十优质品牌涡轮流量计公司推荐
  • 2025 年涡街流量计厂家企业品牌推荐排行榜,实力铸就良好口碑涡街流量计公司推荐
  • 练习篇:从零开始了解网络空间安全(网导1)
  • 2025年粘度计厂家推荐排行榜,在线/旋转/振动/实验室粘度计,反应釜/管线在线粘度计公司推荐!
  • 20232306 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • JAVA基础的ATM机存款项目
  • 对话式AI竞赛决赛队伍揭晓
  • 2025年粉末涂料厂家推荐排行榜,广东粉末,绝缘粉,钣金粉,烤漆粉,专业品质与市场口碑深度解析!
  • Boids算法
  • Spring Cloud RabbitMQ 详解:从基础概念到秒杀实战 - 详解
  • 2025年安装厂家权威推荐榜单:管道/电气/生物医药工厂机电/暖通空调/空压系统/纯水系统/厂房通风/车间配电/机械设备/工业设备安装公司精选
  • 35跬步本手@数学学习+计算机学习+语言学习@20251019
  • 【容器日志采集】【 四】消费kafka保存到es