[DP]BZOJ1566(NOI2009)【管道取珠】题解
题目概述有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i$ 种方案的方案数为 $a_i$ ...
[wqs二分+DP]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告显然是 $O(n^2m)$ DP吧？数据小的可怜，这样就可以过了……不过有一种更好的...
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 $n$ 个员工 $m$ 条矛盾，现在要炒若干个员工的鱿鱼，一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经验BZOJ1312，没权限号就在P...
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑出随意一种最小割（最大流），然后在...
[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解
题目概述题目太复杂了QAQ，自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了 $[L,R]$ ，里面的所有子区间...
[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解
题目概述有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就可以得到这条边的价值。求最大价值。...
最小割模型
对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割：ZOJ2676最大权闭合图给出一张带点权的有向图...
[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解
题目概述有 $n$ 种无数个的物品，每种物品带有ZZK的蒟蒻值 $weak_i$ 和JZ的神犇值 $strong_i$ ，你现在可以选任意个物品，将得到所有物品神犇值之和的JZ神犇值。但是ZZK...
[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解
题目概述有一个 $n$ 个点 $m$ 条双向边的图，每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄，想切断 $1$ 到 $n$ 的连接（切断一条边的代价是这条边的边权）。因为JZ是神犇，...
[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解
题目概述有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖)。问最大的价值。解题报告这是道假...
