CFgym103409E

Alice 和 Bob 在一个有向图上玩游戏，最开始有向图上没有边，Alice 先手买几条边加到图中，之后，Bob 需要从图中删边直到无边。但是 Bob 每次只能删掉一个边集 $S$ ，$S$ 必须是无环的。

有 $m$ 条边，Alice 最多可以买不超过 $c$ 条边，Alice 想要最大化删边轮数，Bob想要最小化删边轮数，两边都是最聪明的，请求出删边轮数。

$n \leq 2000,m \leq 5000$

UVA1146 Now or later

有 $n$ 架飞机需要着陆。 每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一，且必须选择一种。 第 $i$ 架飞机的早着陆时间为 $E_i$，晚着陆时间为 $L_i$，不得在其他时间着陆。 你的任务是为这些飞机安排着陆方式，使得相邻两个着陆时间间隔的最小值（称为安全间隔）应尽量大。

$n \leq 2000,0 \leq t \leq 10 ^ 7$

P2700 逐个击破

一棵树上有 $k$ 个关键点，要求用最小的代价把这些点划分到不s同连通块中。

$2 \leq k \leq n \leq 10^5$

P1772 [ZJOI2006]物流运输

物流公司要把一批货物从码头 1 运到码头 $m$。由于货物量比较大，需要 $n$ 天才能运完，共有 $m$ 个码头。

物流公司会设计一条固定的运输路线，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。

一次修改路线会带来 $k$ 的成本。因此物流公司希望能够订一个 $n$ 天的运输计划，使得总成本尽可能地小。

$n \leq 100,m \leq 20$

经 典 老 番

值得复习

P2169 正则表达式
在Internet网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在A到B的连接不一定存在B到A的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况，他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。

对于100%的数据，$1\leq n\leq200000, 1\leq m\leq 1000000$

题目链接：

P2194 HXY烧情侣

题目描述：

众所周知，HXY已经加入了FFF团。现在她要开始喜（sang）闻（xin）乐（bing）见（kuang）地烧情侣了。这里有$n$座电影院，$n$对情侣分别在每座电影院里，然后电影院里都有汽油，但是要使用它需要一定的费用。$m$条单向通道连接相邻的两对情侣所在电影院。然后HXY有个绝技，如果她能从一个点开始烧，最后回到这个点，那么烧这条回路上的情侣的费用只需要该点的汽油费即可。并且每对情侣只需烧一遍，电影院可以重复去。然后她想花尽可能少的费用烧掉所有的情侣。问最少需要多少费用，并且当费用最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对$1e9+7$取模的结果。

（注：这里HXY每次可以从任何一个点开始走回路。就是说一个回路走完了，下一个开始位置可以任选。所以说不存在烧不了所有情侣的情况，即使图不连通，HXY自行选择顶点进行烧情侣行动。且走过的道路可以重复走。）

[POI2008]BLO-Blockade

有 $n$ 个节点的无向图，定义封锁一个点为切断这个点的所有连边。求每个节点被封锁后图内的不连通有序点对个数。

树链剖分是个很强的 OIer

树链剖分是用来解决一系列树上问题的利器。