图论 *1600~1900

给定一个 $\text{DAG}$，并保证边的方向都是小编号连向大编号。

每个点有点权 $a_i$，$i \to j$ 有边权 $w_{i,j}$。

求一条路径 $v_1 \to v_2 \to ... \to v_k$，满足：

$v_1 = 1$，$v_k = n$，$\sum a_{v_i} \le w_{i,j}$。

求所有情况 $\max w$ 最小的情况。

你发现一共两个条件：

$\sum a_{v_i} \le w_{i,j}$ 和 $\max w$ 最小。

前者可以直接拓扑排序判合法性。

后者一般是按边权排序 $\text{Kruskal}$，看什么时候 $1$ 和 $n$ 连通。

思考一下咋把这两个结合起来，不难发现可以二分 $\max w$，把比它大的边删了，然后用拓扑排序判合法性，就 ok 了。

无向图，问每个点能不能被从 $1$ 开始经过若干步走到，这个若干步是集合做背包做出来的。

你发现可以和邻点来回倒实现让路程 $+2$。

分奇偶讨论，即把一个点拆成奇和偶，从 $1$ 开始 $\text{bfs}$，求到奇步和偶步的最短路。

也就是说如果背包里能凑出一个奇数大于奇步最短路或偶数大于偶步最短路，就是 $1$。

把背包求个 $\sum$，再减去最小的奇数，就分别是最大的奇偶。