luogu P1963

题目链接

注意到 $i$ 和 $t_i$ 是一一对应的关系，可以想到二分图匹配。$t_i$ 可以匹配的 $i$ 可以通过 $D(i, t_i)$ 推断得到，具体为：

• $i \to i + D(i, t_i$;
• $i \to i - D(i, t_i)$;
• $i \to i + D(i, t_i) - n$;
• $i \to i - D(i, t_i) + n$;

然后连边跑匈牙利算法即可。

但是题目还有一个特殊约束，要求输出 字典序最小 的 $t_i$。

我们考虑每次匈牙利算法都是拆散前面的已匹配点，尝试让后面的点和前面的点替换之后能够匹配，我们就可以先给邻接表排序，倒序处理每一个点，这样每次标号小的点都是尝试匹配编号小的点，就可以解决问题。

1
int acpt = 0;
2
for (int i = n; i >= 1; i--) {
3
  memset(visited, false, sizeof(visited));
4
  acpt += hungary(i);
5
}

还有一个要注意的地方是需要输出的是 $t_i$，和匈牙利算法中的 $match_u$ 是相反的，需要重新记录。

code

Luogu P2825

题目链接

首先对原图进行处理，发现每一个被 ’#’ 分割的连续段内可以放置的区域互相影响且最多贡献一个。且行列之间也相互影响，于是可以考虑匹配每一行和没一列的连续段，发现是二分图最大匹配，跑匈牙利算法即可。

code

Luogu P4055

题目链接

和上一题类似，先对原图拆解建边，容易发现对新图二染色后，每次移动只会从白色交替移动到黑色点。 如果原图中存在完美匹配的话，无论从哪个点开始，最后的路径长度一定为偶数，先手必败。

所以我们要找到不在最大匹配中的点作为起始点，这样就翻转了先后手顺序，跑出任意一个最大匹配后搜索即可。注意左右的点都要处理。

code

Luogu P3882

题目链接

首先题目要求 新摆放的棋子不能和原来棋盘上的棋子相互攻击，所以我们定义 $attack_{x, y}$ 表示 $(x, y)$ 这个位置是否会被攻击。

处理完原图摆放的棋子的攻击位置之后，我们还要保证新摆放的棋子不会攻击原来的棋子。发现新摆放的棋子的攻击距离是两条斜线。不如逆向思维一下，发现在原地图上的棋子的两条斜线上摆放新棋子的话就无法满足约束，同意归为 $attack_{x, y}$ 的定义。

现在同 P4055 就很类似了，我们对斜线上进行连续段拆分，跑二分图匹配即可。

code

Luogu P4452

题目链接

考虑以每一个请求为状态构建网络图，对每一个状态拆点，建一条 $(i, i', 1, -w_i)$ 的边，对于那些满足 $t + t_{b_i, 0} \le T$ 的请求，想汇点连一条 $(INF, f_{b_i, 0})$ 的边，对于 $t_{0, a_i} \le t$ 的请求同理。

然后考虑只有 $K$ 架飞机的约束，建立超级源点，向 $0$ 号点连一条流量为 $K$，代价为 $0$ 的边即可。

注意一个 typo，SPFA 里的判断是 $dist_v \le dist_u + cost_i$，而不是 $dist_v < dist_u + cost_i$ (不知道为什么之前好像这么写过但没有被卡掉)。

code

Luogu P5192

题目链接

一看就是一个有源上下界网络流的板子，建模也挺显然的，令 $x(i)$ 表示第 $i$ 天对应的图上的点，$y(i)$ 为 萝莉 少女对应的图上的点，$S$ 为原图的超级源点，$T$ 为超级汇点，建图如下：

• $(S, x(i), 0, d_i)$ 表示每一天最多拍 $d_i$ 张照片；
• $(x(i), y(j), l, r)$ 表示第 $i$ 天，第 $j$ 位少女的拍照数量在 $[l, r]$ 范围内；
• $(y(j), T, g_j, INF)$ 表示第 $j$ 位少女最后至少拍 $g_j$ 张照片。

然后建图跑有源上下界最大流就好了，欸欸，不对，我的上下界网络流的超级源点和超级汇点哪去了？哦哦，还要有超级超级源点和超级超级汇点(应为没写这个调了 30mins)。

code

Luogu P2607

题目链接

发现题目中没有保证给出的图是一棵树，所以我们需要考虑有环的情况，即原图中可能存在基环树（森林）。

直接枚举环上的边是否删除，删除一条边之后就得到了一棵树，对这棵新树做 dp 即可，但是还要考虑断掉的一条边两端端点的情况，两个点只能取一个，所以直接对两个点都做一次 dp，取 $max$ 即可。

code

Luogu P5022

题目链接

不难发现需要对数据范围进行分治，对于前 $60$ 的数据，直接遍历每一个点，然后对其邻接点排序后输出即可。

对于后 $40$ 的数据，发现是一棵基环树，且环上的边肯定有一条是走不了的，枚举边删除即可。复杂度 $O(n^2)$。

code

Luogu P5049

题目链接

和 P5022 类似，但是不能使用 $O(n^2)$ 的枚举算法了，考虑如何更高效地找到环上那条必定不走的边。

发现必定不走的边的编号一定比当前环上所有已遍历的点的编号都大时，这条边就不用走了，回溯即可，具体实现是需要记录一下以走过点的最大编号，然后要对原始边排序后再建图。

code

Luogu P4043

题目链接

一道有源汇的上下界费用可行流板子，把有源汇上下界可行流的最大流改成费用流就可以了。

code

Luogu P4381

题目链接

发现题目中没有保证给出的图是一棵树，需要处理环的问题，我们容易发现如果是一棵树，答案就是森林中每一棵树的直径之和。

考虑处理环上的情况，我们记录 $f_u$ 表示不在环上、在 $u$ 的子树内的距离 $u$ 点最远的距离，然后答案就是 $max(f_u + f_v + dist_{u, v}, f_u + f_v + (len - dist_{u, v}))$ 以及子树中直径长度的最大值。

code

Luogu P1399

题目链接

题目要求选一个点，最小化 $dist(u, S)$，其中 $S$ 为选中的点，但是这个点也可以在边的任意位置。

由此可以发现，这道题还是和树的直径有关系，而和树的中心没什么关系。

我们考虑如何求基环树的 “直径”，可以考虑在环上删除一条边，这样就可以把基环树转换成一棵普通的树形结构，求直径即可。但是这样直接做的复杂度是 $O(n^2)$ 的，无法接受。

我们考虑先钦定一条边删除，然后考虑删除其他边对其的影响即可。对于每个前后缀记录一下 $max_dep$ 和子树内的最大直径，就可以在 $O(1)$ 的时间复杂度内完成转移。

code

Luogu P15410

题目链接

发现位置 $(i, j)$ 只可能移动到 $(n - i + 1, j), (i, m - j + 1), (n - i + 1, m - j + 1)$ 中的一个，所以判断一下每个位置上的是否合法即可。

code

Luogu P3533

题目链接

如果是一棵树的话，就直接求 $LCA(u, v)$ 即可。但是这道题要考虑环的情况（可能有自环，不过无所谓）。用手画一下发现是一棵内向基环树，先用 Topo 找一下环的位置，然后建反向边处理环上子树的信息。

然后分类讨论一下：

• 如果 $u, v$ 不在同一个连通块内，直接输出 -1 -1；
• 如果 $u, v$ 在环上的同一棵子树内，就直接求 $LCA(u, v)$ 即可。
• 否则选择的点只可能在 $rt_u, rt_v$ 中的一个，判断即可。

code

Luogu P4320

题目链接

对原图建出圆方树，容易发现，一定经过的点必定是圆点，又因为圆方树上的圆点和方点都是交替相连，答案即为 $dist(u, v) / 2 + 1$。

code

Luogu P4630

题目链接

考虑如果钦定 $c, f$，$s$ 就可以取这个连通块所有点去掉 $c \to f$ 的路径并。

发现如果在一个点双内，无论怎么取 $s, c, f$，都是合法的。建立圆方树后，去掉 $c, f$ 在树上的路径，剩余的点都可以取为 $s$，但是要分类讨论圆点和方点的情况。

code

Luogu P4334

题目链接

简化题意：

给定一张无向图，有以下两个询问：

• 1 u v g1 g2：判断删除连接 $g1, g2$ 的边之后，$u, v$ 是否联通；
• 2 u v c：判断删除点 $c$ 之后，$u, v$ 是否联通。

不难发现，如果 $(g1, g2)$ 不是割边，$u, v$ 一定可达，$c$ 不是割点同理。

我们建立 dfs 搜索树，在搜索树上用 $dfn_u$ 和 $low_u$ 判断即可。注意割边的判断 $low_{g2} \le dfn_{g1}$ 要取等。

code

Luogu P5236

题目链接

对仙人掌图建圆方树需要注意，可能存在圆圆边，即保留原来搜索树上的边不变。

然后分类讨论一下 $LCA(u, v)$ 是圆点还是方点，如果是圆点，答案就是 $dist_u + dist_v - 2 * dist_{LCA(u, v)}$，否则需要考虑 $u \to LCA(u, v)$ 倒数第二个点是什么，记为 $a$，对于 $v$ 同理，即为 $b$，然后答案就是 $dist_v - dist_b + dist_u - dist_a + min_dist{a, b}$，即考虑 $a, b$ 在点双（环）内的最短路径。

code