[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解
题目概述题目太复杂了QAQ，自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了 $[L,R]$ ，里面的所有子区间...
[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解
题目概述有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就可以得到这条边的价值。求最大价值。...
最小割模型
对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割：ZOJ2676最大权闭合图给出一张带点权的有向图...
[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解
题目概述有一个 $n$ 个点 $m$ 条双向边的图，每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄，想切断 $1$ 到 $n$ 的连接（切断一条边的代价是这条边的边权）。因为JZ是神犇，...
