[最小割+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$ 则没有依赖)。问最大的价值。解题报告这是道假...
[裴蜀定理]BZOJ2299(HAOI2011)【向量】题解
题目概述问能否用任意个向量 $(\pm a,\pm b)$ 和 $(\pm b,\pm a)$ 组合出向量 $(x,y)$ 。
[树状数组]BZOJ3192(JLOI2013)【删除物品】题解
题目概述一共有两堆物品，分别有 $n$ 个和 $m$ 个。所有物品都是一样的，但是它们有不同的优先级。只能够移动某堆中位于顶端的物品，你可以把任意一堆中位于顶端的物品移动到另外一堆的顶端。若此物...
欢迎来到ZigZagK的博客！
欢迎来到ZigZagK的博客！（其实这只是个测试页面）是时候丢弃CSDN了。——By Lynstery$\LaTeX$ :我们来求个 $LIS$ 吧 $f(i)=max\{f(j)|j<...
