menu ZigZagK的博客

正在努力加载中QAQ

[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树,有 $m$ 种取节点的方法,第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ,$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[二分+上下界费用流]HDU5263【平衡大师】题解
题目概述有 \(n\) 个点 \(m\) 条单向边,每个点的不平衡度为出度减入度的差的绝对值,现在可以删除至多 \(m-K\) 条边,求最大不平衡度的最小值。
apps HDU
local_offer 查看标签
comment 0 条评论
remove_red_eye 339 次访问
阅读全文
[最小割]TopCoder【FoxAndCity】题解
题目概述有 \(n\) 个由双向边连通的城市,\(1\) 号城市里住着神犇JZ。\(i\) 号城市想要离JZ所在城市距离为 \(want_i\) ,如果实际的距离为 \(real_i\) ,那么...
apps TopCoder
local_offer 查看标签
comment 0 条评论
remove_red_eye 69 次访问
阅读全文
[最小割]BZOJ3144(Hnoi2013)【切糕】题解
题目概述有一块 \(X\times Y\times Z\) 的切糕,每个点 \((x,y,z)\) 都有不和谐值 \(v(x,y,z)\) 。现在要切这块切糕,为每个直线 \((x,y)\) 选...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 75 次访问
阅读全文
[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解
题目概述有 \(n\) 个神犇JZ,某两个JZ配合有神犇值,共有 \(m\) 组这样的JZ。现在要选出若干个JZ(假设选了 \(k\) 个),贡献为存在于这些JZ中的所有配合的神犇值之和除以 \...
apps 计蒜客
local_offer 查看标签
comment 0 条评论
remove_red_eye 52 次访问
阅读全文
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 \(n\) 个员工 \(m\) 条矛盾,现在要炒若干个员工的鱿鱼,一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。
apps POJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 70 次访问
阅读全文
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 \(n\) 个点 \(m\) 条有向边的图,现在要求 \(S,T\) 的最小割,问每一条边: 有没有可能出现在最小割中。 是否一定出现在最小割中。 解题报告先跑出随意一种...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 57 次访问
阅读全文
[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解
题目概述题目太复杂了QAQ,自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件,发现带有很多“强制”操作,比如吃了 \([L,R]\) ,里面的所有子...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 47 次访问
阅读全文
[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解
题目概述有 \(n\) 个点 \(m\) 条边,每个点需要花费 \(p_i\) 购买,每条边可以得到 \(c_i\) 的价值。现在要购买一些点,如果一条边两端的点都被购买了,就可以得到这条边的价...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 77 次访问
阅读全文
最小割模型
对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割:ZOJ2676最大权闭合图给出一张带点权的有向图...
apps 图论
local_offer 查看标签
comment 1 条评论
remove_red_eye 105 次访问
阅读全文
keyboard_arrow_up