[分数规划+长链剖分+线段树]洛谷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是神犇，...
