ZigZagK的博客
[分数规划+长链剖分+线段树]洛谷4292【[WC2010]重建计划】题解
题目概述洛谷4292解题报告题解里很多点分治,但其实用长链剖分十分的直白。首先先用01分数规划,二分答案 $mid$ ,然后问题转化为边权为 $w-mid$ 的树上选出一条和 $\ge0$ 且长...
[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解
题目概述有 $n+1$ 个人,选第 $i$ 个人需要花费 $s_i$ ,得到 $p_i$ 的贡献,第一个人必选,没有花费和贡献。$2\sim n+1$ 都有一个推荐人(推荐人编号小于自己的编号)...
[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解
题目概述有 $n$ 个神犇JZ,某两个JZ配合有神犇值,共有 $m$ 组这样的JZ。现在要选出若干个JZ(假设选了 $k$ 个),贡献为存在于这些JZ中的所有配合的神犇值之和除以 $k(2n-k...
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 $n$ 个员工 $m$ 条矛盾,现在要炒若干个员工的鱿鱼,一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经验BZOJ1312,没权限号就在P...
[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解
题目概述有一个 $n$ 个点 $m$ 条双向边的图,每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄,想切断 $1$ 到 $n$ 的连接(切断一条边的代价是这条边的边权)。因为JZ是神犇,...