Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
AtCoder Beginner Contest 332 G. Not Too Many Balls(最大流转最小割 dp)
题目 n n lt 500 种球 第i种有ai 0 lt ai lt 1e12 个球 m m lt 5e5 个盒子 第j个能放bj 0 lt bj lt 1e12 个球 特别地 第j个盒子最多能放i j个第i种球 求m个盒子能放的最多的球的
基础dp(线性dp计数dp递推dp子序列dp)
网络流费用流
DP
最大流
最小割
PowerOJ 2543: 赛场布置
题目链接 对于每个点 它可以选择男或者女 如果要加上的贡献 那么相邻的一定得是异性才可以 所以 对相邻的 我们可以考虑成 然后 我们对于点坐标的的奇偶性分别讨论即可 当然 还需要考虑的贡献 然后就是全选减去最少割去的即可 include
网络流
最小割
最大流
Interval【对偶图优化最小割(最大最小定理 周冬)】
2020牛客多校第二场I题 首先 我们考虑最小割的方式来处理该问题 很明显的 这就是一张对偶图了 因为它没有任意两线会存在相交的可能了 所以根据对偶图的做法 我们可以将最小割问题转化为最短路了 绿色和粉色是新的对偶图所构成的边和点 然后我们
网络流
对偶图
最小割
最短路
【SHOI2017】寿司餐厅【最大权闭合子图】
题目链接 说实话 这道题从前天开始敲 然后不断的加优化 今晨才过了它 但是却对于最大权闭合子图有了很深的了解 题意 有N种寿司 我们可以吃连续的一段寿司 讲 将得到一系列的贡献 譬如说吃了1 2 3三个寿司 将得到 这么多的贡献值 当然 每
网络流
图论
最大权闭合子图
最小割
最大流