[二分+上下界费用流]HDU5263【平衡大师】题解

题目概述有 \(n\) 个点 \(m\) 条单向边,每个点的不平衡度为出度减入度的差的绝对值,现在可以删除至多 \(m-K\) 条边,求最大不平衡度的最小值。     阅读全文
ZigZagK 2018年4月19日 16:03
0 评论 | 110 访问

[最小割]TopCoder【FoxAndCity】题解

题目概述有 \(n\) 个由双向边连通的城市,\(1\) 号城市里住着神犇JZ。\(i\) 号城市想要离JZ所在城市距离为 \(want_i\) ,如果实...     阅读全文
ZigZagK 2018年4月15日 20:50
0 评论 | 26 访问

[最小割]BZOJ3144(Hnoi2013)【切糕】题解

题目概述有一块 \(X\times Y\times Z\) 的切糕,每个点 \((x,y,z)\) 都有不和谐值 \(v(x,y,z)\) 。现在要切这块...     阅读全文
ZigZagK 2018年4月11日 23:22
0 评论 | 39 访问

[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解

题目概述有 \(n\) 个神犇JZ,某两个JZ配合有神犇值,共有 \(m\) 组这样的JZ。现在要选出若干个JZ(假设选了 \(k\) 个),贡献为存在于...     阅读全文
ZigZagK 2018年4月7日 15:59
0 评论 | 15 访问

[最大密度子图]POJ3155【Hard Life】题解

题目概述有 \(n\) 个员工 \(m\) 条矛盾,现在要炒若干个员工的鱿鱼,一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。     阅读全文
ZigZagK 2018年3月14日 14:28
0 评论 | 27 访问

[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解

题目概述题目太复杂了QAQ,自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件,发现带有很多“强制”操作,比如...     阅读全文
ZigZagK 2018年3月10日 15:41
0 评论 | 17 访问

[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解

题目概述有 \(n\) 个点 \(m\) 条边,每个点需要花费 \(p_i\) 购买,每条边可以得到 \(c_i\) 的价值。现在要购买一些点,如果一条边...     阅读全文
ZigZagK 2018年3月8日 21:14
0 评论 | 38 访问

最小割模型

对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割:ZOJ2...     阅读全文
ZigZagK 2018年3月8日 20:14
1 评论 | 45 访问

[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解

题目概述有一个 \(n\) 个点 \(m\) 条双向边的图,每条边的边权是 \(w_i\) 。JZ为了防止神犇之力外泄,想切断 \(1\) 到 \(n\)...     阅读全文
ZigZagK 2018年3月7日 18:32
0 评论 | 15 访问