首页 > 其他分享 >POI2009GAS-Fire Extinguishers

POI2009GAS-Fire Extinguishers

时间:2024-04-18 09:12:10浏览次数:22  
标签:tmp cnt Fire per int dfs rm POI2009GAS Extinguishers

POI #Year2009 #贪心

贪心的把灭火器放到深度较小的点上,对于每个点,维护两个数组,记录距离当前点为 \(x\) 没有覆盖的点有 \(a_x\)个,距离当前点\(y\) 的灭火器有 \(b_y\) 个

然后在每个点上,合并长度为 \(len\) 或者 \(len-1\) 的路径,因为这些路径不能延伸到父节点,所以要在这个点解决

如果当前点的 \(a_{len}>0\) 那么考虑在当前点放灭火器覆盖这些点,然后更新 \(b\)

注意特判在 \(1\) 上时要将所有可以的全部覆盖上,而不限制覆盖的长度

// Author: xiaruize
const int N = 1e5 + 10;

int n, s, k;
vector<int> g[N];
int cnt[N][25], rm[N][25];
int res = 0;

void dfs(int x, int fa)
{
	cnt[x][0]++;
	for (auto v : g[x])
	{
		if (v == fa)
			continue;
		dfs(v, x);
		rep(i, 0, k - 1)
		{
			cnt[x][i + 1] += cnt[v][i];
			rm[x][i + 1] += rm[v][i];
		}
	}
	per(i, k, 0)
	{
		per(j, k - i, max(0, k - i - 1))
		{
			int tmp = min(cnt[x][i], rm[x][j]);
			cnt[x][i] -= tmp;
			rm[x][j] -= tmp;
		}
	}
	if (cnt[x][k])
	{
		int tmp = (cnt[x][k] + s - 1) / s;
		rm[x][0] += tmp * s;
		res += tmp;
	}
	per(i, k, 0)
	{
		per(j, k - i, max(0, k - i - 1))
		{
			int tmp = min(cnt[x][i], rm[x][j]);
			cnt[x][i] -= tmp;
			rm[x][j] -= tmp;
		}
	}
	// debug(x, res, cnt[x], rm[x]);
}

void solve()
{
	cin >> n >> s >> k;
	rep(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	int x = 1;
	per(i, k, 0)
	{
		per(j, k - i, 0)
		{
			int tmp = min(cnt[x][i], rm[x][j]);
			cnt[x][i] -= tmp;
			rm[x][j] -= tmp;
		}
	}
	int tmp = 0;
	rep(i, 0, k) tmp += cnt[1][i];
	cout << res + (tmp + s - 1) / s << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签:tmp,cnt,Fire,per,int,dfs,rm,POI2009GAS,Extinguishers
From: https://www.cnblogs.com/xiaruize/p/18142216

相关文章

  • python命令行工具:fire
    fire 是一个由Google开源的Python库,它能自动将Python代码转换成命令行接口(CommandLineInterface,CLI)。fire 库极大地简化了从Python函数或类生成命令行工具的过程。特性易用性:fire 是为了简化命令行工具的创建而设计的,它可以自动从任何Python对象生成命令行接口......
  • FireDAC将UniDBGrid数据另存为网页HTML格式,方便导出
    procedureDBGrid1ToHTML(aFDquery:TFDQuery;aHTMLFileName:string);varaHTMLtext:TstringList;j:integer;beginaHTMLtext:=TstringList.Create;aHTMLtext.Add('<!DOCTYPEHTMLPUBLIC"-//W3C//DTDHTML4.01Transitional//EN"&......
  • iptables和firewalld的区别
    iptables与firewalld的区别1),firewalld可以动态修改单条规则,动态管理规则集,允许更新规则而不破坏现有会话和连接。而iptables,在修改了规则后必须得全部刷新才可以生效;2),firewalld使用区域和服务而不是链式规则;3),firewalld默认是拒绝的,需要设置以后才能放行。而iptables默认是允许的,需......
  • Firefox火狐浏览器控制台,提示:已拦截跨源请求:同源策略禁止读取位于 http://127.0.0.1
    前言全局说明Firefox火狐浏览器控制台,提示:已拦截跨源请求一、火狐官方说明https://developer.mozilla.org/zh-CN/docs/Web/HTTP/CORS/Errors/CORSMissingAllowOrigin?utm_source=devtools&utm_medium=firefox-cors-errors&utm_campaign=default二、修改浏览器方法[原文......
  • 在Linux中,iptables和firewalld两种防火墙如何使用?
    在Linux中,iptables和firewalld是两种常用的防火墙工具,它们用于配置和管理系统的网络流量。它们都提供了对数据包的过滤、转发和网络地址转换(NAT)等功能。1.iptablesiptables是Linux内核的防火墙组件,它提供了一个命令行界面来设置数据包过滤规则。iptables使用表(tables)和链(chains......
  • FirewallD 没有运行
      如果FirewallD没有运行,说明防火墙服务并没有在CentOS7上启动。这可能会导致无法通过网络连接到虚拟机的服务。你可以按照以下步骤来启动FirewallD服务并开放端口:1.**启动FirewallD服务**:使用以下命令启动FirewallD服务:```bashsudosystemctlstartfirewalld`......
  • AMD_Ubuntu_Docker部署firefox
    AMD_Ubuntu_Docker部署firefox下载driverhttps://github.com/mozilla/geckodriver/releasesfirefox好像跟chrome不一样高版本的geckodriver可以兼容低版本的firefox所以理论上应该节约了很大的工作量.https://www.mozilla.org/zh-CN/firefox/linux/https://downl......
  • [转]Docker部署Firefox容器,实现远程浏览器查看内网服务,如登录路由器配置页面等
    类似的镜像很多人都做过,找了一个start数比较多的jlesage/firefox,这个在github上有详细使用说明,我使用docker-compose.yml文件内容如下:version:'3'services:firefox:container_name:firefoximage:jlesage/firefoxports:-"5800:5800"volu......
  • linux中防火墙设置(iptables & firewalld & ufw )
       iptables、firewalld和ufw都是Linux系统中常用的防火墙软件,它们之间的区别如下:   iptables:iptables是Linux系统中最原始、最基础、最底层的防火墙软件,它可以直接配置Linux内核中的网络规则,控制网络数据包的流动。由于iptables配置比较复杂,需要对网络协议和规则有......
  • 启动应用程序出现FirewallAPI.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个FirewallAPI.dll文件(挑选合适的版本文件)把......