P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus
题意
给定一个含有 \(N\) 个点，\(M\) 条边的有向图，每条边从 \(U_i\) 指向 \(V_i\)，经过这条边的代价为 \(C_i\)。
在最开始时，我们可以翻转至多一条边，即让这条边从 \(U_i\to V_i\) 永久变为 \(V_i\to U_i\)，并产生 \(D_i\) 的代价。你要从点 \(1\) 到点 \(N\)，再从点 \(N\) 回到点 \(1\)，你想知道，通过翻转至多一条边，能得到的最小代价和为多少？
其中 \(N\le 200,M\le 5e4\)
思路
考虑翻转一条边会对最短路径造成什么影响，可以相当于添加一条边、删除一条边。
在添加一条边时，设新加的边为 \(v\to u\)，原 \(1\to n\) 的最小代价为 \(ans_1\)，原 \(n\to 1\) 的最小代价为 \(ans_2\)，从 \(x\) 到 \(y\) 的最短距离为 \(dis_{x,y}\)。那么此时能够产生的新代价为 \(\min(ans_1+dis_{n,v}+dis_{u,1}+c_i+d_i,dis_{1,v}+dis_{u,n}+c_i+d_i+ans_2)\)。（若 \(dis_{1,v}\) 或 \(dis_{n,v}\) 经过了 \(u\to v\) ，那么答案一定不优，因为我们会经过这条边两次）
在删除一条边时，若原边不在 \(1\to n\) 和 \(n\to 1\) 的最短路径上，那么此时改变这条边时，原 $ 1 \leftrightarrows u,v \leftrightarrows n$ 的最短路径不变，仍然可以直接继承以前的答案 \(ans_1,ans_2\)。但是若处于最短路径上，此时原答案会改变，所以我们还是需要再跑一遍最短路。考虑到最短路径上只会最多有 \(2n\) 条边，因此，这样的时间复杂度为 \(n\times m+n\times (m+n)\times \log(n+m)=n^3\) 。
AT_arc107_f [ARC107F] Sum of Abs
题意
有一个包含 \(N\) 个顶点和 \(M\) 条边的简单无向图，每个顶点 \(i\) 上写有两个整数 \(A_i, B_i\)。
可以选择删除 \(0\) 个或多个顶点。删除顶点 \(i\) 的代价为 \(A_i\)，与被删除顶点相连的边也会被同时删除。删除完顶点后，得分的计算方式如下：
- 总得分等于所有连通分量得分的总和。
- 某个连通分量的得分为该分量内所有顶点的 \(B_i\) 之和的绝对值。
收益定义为 \((\)总得分 \(-\) 删除顶点的总代价\()\)，求出最大收益。
其中 \(N\le 300,M\le 300\)
思路
我们最想做到的肯定是负数在同一个连通分量里，正数在同一个连通分量里。但这种情况不一定是最优方案。直接删点我们发现连通性不好判断，所以可以考虑 时间倒流，先花费全部代价把所有点都删掉，再一个一个加入。
此时加入一个点 \(i\) 的代价就变到了 \(a_i+b_i\) 或 \(a_i-b_i\)（因为此时若所处集合总权值 \(<0\) ，那么加入一个点的代价即为 \(-b_i\) ）。计前面的点为 \(i^+\) ，后面的点为 \(i^-\) 。
显然两个点不能都被选入集合。这样的形式很像独立集。
一个集合内的点要么全为 \(i^+\) ，要么全为 \(i^-\)，这个限制依然是不好考虑的，可以考虑如何转化成上面的限制。对于一条边 \(u\to v\) ，有限制 \(u^+\nrightarrow v^-\) ，\(u^-\nrightarrow v^+\) ，与上面同理。
二分图最小权点覆盖集
点覆盖集指选择一些点，这些点能够与图中的所有边连接。可使用网络流最小割来处理，具体的，若一个点的权值 \(\le0\) ，显然可以直接选择该点。对于剩下的点，让 \(s\) 向 \(A\) 集合的点连一条权值为点权的边，\(A\) 到 \(B\) 连一条无穷大的边，\(B\) 向 \(t\) 连一条权值为点权的边，此时在这张图中求最小割即可求出答案，正确性显然。
二分图最大权独立集
经过上面的点覆盖集，那么我们若不选这些位于点覆盖集的点，那么剩下的点一定可以组成一个点独立集（任意两点之前都不存在边），证明可以考虑我们若删去和这些点独立集内的点相连的边，那么此时所有边都会被删除。那么此时的最大权独立集即为总点权 \(-\) 最小权点覆盖集。
那么对于原题目，此时我们的总点权为 \(2\times \sum a_i\) ，让所有的 \(i^+\) 向 \(i^-\) 连一条无穷大的边，\(s\) 向 \(i^+\) 连一条点权边， \(i^-\) 向 \(t\) 连一条点权边， 对于一条边 \(u\to v\) 同理连不同号之间的无穷大边，此时在原图中求最小割即为最小权点覆盖集的大小，此时用 \(2\times \sum a_i-\) 该权值 即为最大权独立集大小，再减去一开始删点的代价。
如果 \(i^+\) 和 \(i^-\) 都被删去了，此时的代价变为 \(2a_i-(a_i+b_i)-(a_i-b_i)-a_i\) ，可以发现正好等于删去该点的代价。
uoj605 知识网络
题意
一张图上有 \(n\) 个点，其中每个点都有一个标签，标签总数为 \(k\) ，求出全源最短路，输出每一种路径长度的路径条数。
其中 \(n\le 5e4,k\le 150\)
思路
最暴力的做法是把所有点都跑一遍最短路，时间复杂度 \(O(n\times (n+m))\)
数据范围提示我们去考虑每一个标签内的情况，把该标签内所有的点都与其他非此标签点求出最短距离，显然的是，标签内的点到其他任意一个点的最短路径距离之差不会超过 \(1\) 。
所以可以利用这一特性，对于每一个点都暴力求出该标签内有多少个点能够在最短路DAG上到达他。不妨把所有该标签的点称为 关键点 。具体的，我们可以拿 bitset 来实现这个过程，当 \(x\) 是 \(y\) 在最短路径图上的前驱时，把能够到达 \(x\) 的所有点继承到 \(y\) 点上。
关于空间限制 \(256Mb\) ，我们可以选择把一个标签内的点分多次跑完。
P3227 切糕
题意
给定一个 \(p*q*r\) 的长方体，每个 \(1*1*1\) 方块上都有一个权值 \(v_{i,j,k}\)，现在要对所有的第 \(x\) 行第 \(y\) 列的方块钦定一个高度 \(h(x,y)\)，满足相邻四个 \(h(x,y)\) 的绝对值之差不得超过 \(D\)，求出能够实现的所有权值之和中最小值。
其中 \(p,q,r\le 40\)
思路
可以转化成网络流模型，显然要用最小割处理。对于一个点 \((i,j,k)\)，我们显然可以连出这样几条边
- \((i,j,k)\to (i,j,k+1)\)，边权为 \(v_{i,j,k}\)
- \((i,j,k)\to(i,j,k-1)\)，边权为 \(\inf\)
- \((i,j,k)\to (i+1,j,k-D)\dots\)，边权为 \(inf\)
- \(S\to (i,j,1)\) ，边权为 \(inf\)
- \((i,j,r)\to T\) ，边权为 \(v_{i,j,r}\)
其中，第一类边显然是方便我们进行最小割，第二类边是为了控制我们只能割掉一条链上的一条边，第三类边是为了控制绝对值之差。
但是，为什么第二类边能够控制绝对值之差？
引理：我们若割掉一条边 \(u\to v\)，那么肯定有 \(s\to u\to v\to t\) 。
那么我们就可以考虑下面的这张图了：
在这张图上，我们在同一条链上割掉了两条边 \(x_1\to y_1\)， \(x_2\to y_2\)，那么按照上面的引理，\(S\) 能到达 \(x_2\) ，\(T\) 能到达 \(y_1\) ，我们的第二类边就可以直接让 \(S\to T\) 了，显然不合法。
P5332 [JSOI2019] 精准预测
题意：
目前，火星小镇上有\(n\)个居民（编号\(1,2,……,n\)）。机器学习算法预测出这些居民在接下来\(T\)个时刻（编号\(1,2,……,T\)）的生死情况，每条预测都是如下两种形式之一：
-
难兄难弟\(0\) \(t\) \(x\) \(y\)：在\(t\)时刻，如果\(x\)是死亡状态，那么在\(t+1\)时刻，\(y\)是死亡状态。
-
死神来了\(1\) \(t\) \(x\) \(y\)：在\(t\)时刻，如果\(x\)是生存状态，那么在\(t\)时刻，\(y\)是死亡状态。
JYY 希望为每个火星人\(k\)计算
其中 \(\operatorname{Live}(i,j)=1\) 表示编号为\(i\)和\(j\)的火星人有可能同时在第 \(T+1\) 时刻处于生还状态，否则\(\operatorname{Live}(i,j)=0\)。注意火星人是不能够复活的。一个火星人可能在时刻\(1\)就处于死亡状态，也有可能有预测未覆盖的死亡情况发生。
其中 \(1\le T\le 1e6,1\le n\le 5e4,1\le m\le 1e5\)
思路：
一眼想到 2-sat 问题，