[DP]BZOJ1566(NOI2009)【管道取珠】题解

题目概述有两个管道,第一个有 \(n\) 个黑白珠子,第二个有 \(m\) 个黑白珠子,每次可以从一个管道取出最靠管道口的珠子。假设有 \(k\) 中取珠...     阅读全文
ZigZagK 2018年3月29日 21:04
0 评论 | 14 访问

[wqs二分+DP]POJ1160【Post Office】题解

题目概述有 \(n\) 个村庄,现在要建 \(m\) 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。     阅读全文
ZigZagK 2018年3月15日 15:54
0 评论 | 52 访问

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

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

[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解

题目概述给出一张 \(n\) 个点 \(m\) 条有向边的图,现在要求 \(S,T\) 的最小割,问每一条边: 有没有可能出现在最小割中。 是否一定出现在...     阅读全文
ZigZagK 2018年3月12日 15:45
0 评论 | 15 访问

[最大权闭合图]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 评论 | 37 访问

最小割模型

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

[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解

题目概述有 \(n\) 种无数个的物品,每种物品带有ZZK的蒟蒻值 \(weak_i\) 和JZ的神犇值 \(strong_i\) ,你现在可以选任意个物...     阅读全文
ZigZagK 2018年3月7日 19:35
0 评论 | 14 访问

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

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

[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解

题目概述有 \(n\) 个软件和 \(m\) 的容量,每个软件需要 \(w_i\) 的容量,有 \(v_i\) 的价值,同时依赖 \(d_i\) 软件( ...     阅读全文
ZigZagK 2018年3月5日 13:56
0 评论 | 10 访问