[BZOJ 3144][HNOI 2013] 切糕
2024-10-08 19:36:39
题目大意
切糕是 (p times q times r) 的长方体,每个点有一个违和感 (v_{x, y, z})。先要水平切开切糕(即对于每个纵轴,切面与其有且只有一个交点),要求水平上相邻两点的切面高度差小于等于 (D),求切面违和感和的最小值。
(1 leqslant p, ; q, ; r leqslant 40)
(0 leqslant v leqslant 1,000)
题目链接
题解
最小割。
用边连接相邻两个高度的的点,边 ((x, y, z - 1) rightarrow (x, y, z)) 容量为 (v_{x, y, z}),由源点发散出边连接第一层的每个点,最后一层的点收缩在汇点,这是没有(D)的限制是的答案。连接所有形如 ((x, y, z) rightarrow (x, y, z - D)) 的边,这样,当水平相邻的两个点切面差大于 (D) 时,最小割的图会由这样的边连在一起而没有被隔开。
代码
1 |
#include <climits> |
最新文章
- CLR via C# 3rd - 07 - Constants and Fields
- oracle创建用户并导入dmp文件
- js里slice,substr和substring的区别
- python学习之for语句
- PHP正则匹配邮件地址、URL
- EL表达式 functions String处理函数
- python学习之list
- WinFom解决最小化最大化后重绘窗口造成闪烁的问题
- 201521123034《Java程序设计》第十四周学习总结
- div外观例子
- Tomcat集群如何同步会话
- pmi-ACP考试知识点梳理(部分)
- 好的UI管理后台
- 认识Jmeter工具
- LeetCode(95): 不同的二叉搜索树 II
- DOM操作的概念
- php协程
- enum使用方法
- jsoup解析网页出现转义符问题
- 百度地图Map属性和方法
热门文章
- 第二季第十一天 html5语义化标签 css透明度
- Covisibility Graph
- Spring和MyBatis的集成
- 小程序外链跳转web-view系列问题
- 吴裕雄--天生自然 PYTHON3开发学习:输入和输出
- 发布订阅--DBMS ";无法作为数据库主体执行,因为主体“dbo”不存在、无法模拟这种..........”
- 通过javascri实现输入框只能输入数字
- java threadlocal 背景 本质
- VS IDE调试下将打印日志输出到输出窗口
- 看了这个Java实习生入职测试题后,幸亏我不是实习生