[离线+分块+Tarjan缩点+bitset维护传递闭包]The 19th Zhejiang Provincial Collegiate Programming Contest K【Dynamic Reachability】题解
题目概述CF GYM103687K解题报告科技题过于困难。考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2BLK$ 个点。这样就可以大大减小...
[二分图增广路+Tarjan]BZOJ2140【稳定婚姻】题解
题目概述有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP解散之后还能否使得所有人都找到新C...
[Tarjan+拓扑]HDU6165【FFF at Valentine】题解
题目概述问一张 $n$ 个点 $m$ 条有向边的图是否满足两两点 $x,y$ 之间均有 $x$ 与 $y$ 连通或 $y$ 与 $x$ 连通。解题报告FFF团还管这么多？不是直接烧吗？显然一个强...
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑出随意一种最小割（最大流），然后在...
[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解
题目概述有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖)。问最大的价值。解题报告这是道假...
