[思维+最大费用最大流]ACL Contest 1C【Moving Pieces】题解
题目概述ACL Contest 1C解题报告这题还是挺可做的，首先考虑棋子之间拦路的问题，在一颗棋子穿过了另一颗棋子时，我们可以认为两颗棋子互换位置，显然移动次数不变。既然没有棋子之间互相拦路，...
[最大费用可行流]BZOJ5403【marshland】题解
题目概述有 $n\times n$ 的网格，如果 $(i,j)$ 满足 $i+j$ 是奇数那么这个格子就有危险度，现在可以放 $m$ 个占地为 $3$ 的 $L$ 型的石头，石头拐点处的危险度会...
[最小割]TopCoder【SurroundingGame】题解
题目概述有 $n\times m$ 的网格，有两种方法占领一个格子：1.花费 $c_{i,j}$ 。2.该格子上下左右的格子已经被占领。占领一个格子之后有 $b_{i,j}$ 的收益，求收益减去...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[二分+上下界费用流]HDU5263【平衡大师】题解
题目概述有 $n$ 个点 $m$ 条单向边，每个点的不平衡度为出度减入度的差的绝对值，现在可以删除至多 $m-K$ 条边，求最大不平衡度的最小值。解题报告其实不难吧……只是水平限制了我的想象力…...
[最小割]TopCoder【FoxAndCity】题解
题目概述有 $n$ 个由双向边连通的城市，$1$ 号城市里住着神犇JZ。$i$ 号城市想要离JZ所在城市距离为 $want_i$ ，如果实际的距离为 $real_i$ ，那么就会有 $(want...
[最小割]BZOJ3144(Hnoi2013)【切糕】题解
题目概述有一块 $X\times Y\times Z$ 的切糕，每个点 $(x,y,z)$ 都有不和谐值 $v(x,y,z)$ 。现在要切这块切糕，为每个直线 $(x,y)$ 选出一个点 $z$...
[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解
题目概述有 $n$ 个神犇JZ，某两个JZ配合有神犇值，共有 $m$ 组这样的JZ。现在要选出若干个JZ（假设选了 $k$ 个），贡献为存在于这些JZ中的所有配合的神犇值之和除以 $k(2n-k...
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 $n$ 个员工 $m$ 条矛盾，现在要炒若干个员工的鱿鱼，一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经验BZOJ1312，没权限号就在P...
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑出随意一种最小割（最大流），然后在...
