图论建模

ABC437G

ABC437G - Colorful Christmas Tree

一道题建了三个新图，算上原树总共四个图 ww

• 给定 $N$ 点树，每个节点初始被染成 012 三种颜色之一。
• 执行以下操作 $N-1$ 次：选择一条当前存在、且两端点颜色不同的边，将其删除，然后将这条边两端点的颜色，按照 0 $\to$ 1 $\to$ 2 $\to$ 0 的循环顺序变为下一种颜色。
• 判断是否存在一种合法的删边顺序，能够把树上的边全部删完。若存在，输出之。

Step.1 转化为匹配

在全过程中，顶点 $v$ 处于颜色 $k$ 时参与删除，这个操作次数确定，记为 $A_{v, k}$。这给定了每个点在特定颜色下需要消耗的额度，因此这本质上是一个匹配问题。

建图：

• 点：将一个点 $v$ 拆成 $A_{v,k}$ 个点 $(v,k)$。
• 边：对于一条边 $u-v$，如果 $(u,k_{1})$ 和 $(v,k_{2})$ 颜色不同，则连边 $(u, k_1)-(v, k_2)$。

在这张新图上，若能做到完美匹配，才可能有解。

Step.2 转化为最大流

注意到树是一张 二分图 （将树按深度的就奇偶性拆分为左部点和右部点），转化后的新图也是二分图， 匹配可以转化为最大流求解。

建图：

• 点：
  • 源点 $s$ 和汇点 $t$。
  • 对于树上的每一个节点 $v$，在网络中拆分成 3 个状态节点 $(v, 1), (v, 2), (v, 3)$。
• 边：
  • 对于所有偶数深度的点 $u$，$s\to(u, k)$，容量 $A_{u, k}$，表示操作次数限制。
  • 对于所有奇数深度的点 $u$，$(v, k)\to t$，容量 $A_{v, k}$，表示操作次数限制。
  • 对于一条边 $u-v$，若 $u$ 为偶数深度，$v$ 为奇数深度，且 $(u,k_{1})$ 和 $(v,k_{2})$ 颜色不同，则 $(u, k_1)\to(v, k_2)$，容量 1，表示合法匹配。

下面证明，原问题有解 $\iff$ 最大流等于 $N-1$。

Step.3 转化的充要性

必要性：如果存在一种合法的删边顺序，那么对应的每次操作都能找到一条从源点到汇点的路径，这时最大流必定等于 $N-1$。

充分性：只需构造一组解。如果能将 时间先后限制 建出一张有向图，并证明它是 DAG，那么其拓扑序就是所需操作序列。

建图：

• 点：原树的 $N-1$ 条边。
• 边：即 依赖关系 。对于原树中的顶点 $v$，其颜色变换是有顺序的，这就给 $v$ 上的所有相连边规定了一个局部时间先后顺序。如果边 $e_A$ 分配到的颜色比 $e_B$ 的颜色更早出现，我们就连一条有向边 $e_A \to e_B$， 表示 $e_A$ 必须在 $e_B$ 之前被删除 。 当然，如果 $e_A$ 分配到的颜色与 $e_B$ 的颜色相同，这个顺序可以任意交换，我们钦定了一个删除顺序并无妨。

下面只需要证明新图无环。

反证，假设存在一个有向环：$e_1 \to e_2 \to e_3 \dots \to e_k \to e_1$。根据我们的建图规则，每一步 $e_i \to e_{i+1}$ 必定发生在这两条边的公共顶点上，记这个公共点为 $v_{i}$。我们将环上的共享顶点按顺序写出来，合并去重，得到一条 walk $v_1, v_2, \dots, v_k, v_1$。

假设 $k=1$，即全部操作发生在一个点 $v_{1}$ 上，这操作当然不可能出现环。

否则，考虑到这是一棵树，如果能找到这样的一个 walk，必然在一个地方掉头了，即存在 $a\to b\to a$ 的片段。这意味着，我们先删除了边 $a-b$，之后又删除了边 $b-a$。

然而，考虑最大流的性质：任何满流方案中，边 $a-b$ 只会被删除恰好 1 次，它在整个时间线上只对应唯一的一个事件，就不可能在依赖环中出现两次。出现了矛盾。

因此假设不成立，新图是 DAG。其拓扑序就是所需操作序列。

ABC461G

ABC461G - Graph Problem 2026

$N$ 点 $M$ 边简单无向图，在点权 $w$ 满足如下条件时，求 $\sum{w_*}$ 的最大值。

• 对每个点 $i$，$w_i \in \lbrace 0, 1, 2 \rbrace$。
• 对每个边 $(u,v)$，$w_{u}+w_{v} \in \lbrace 0, 1, 2 \rbrace$。

拆点，令 $w_{i}=w_{i_{0}}+w_{i_{1}}$，并钦定 $w_{i_{0}},w_{i_{1}} \in \lbrace 0, 1 \rbrace$，问题将三个权选择化为每个点的选与不选。希望所选点最多。

考虑边的约束 $w_{u_{0}}+w_{u_{1}}+w_{v_{0}}+w_{v_{1}} \in \lbrace 0, 1, 2 \rbrace$，拆分：

• $2,0 = 1,0 + 1,0$，选 $u_0, u_1$，不选 $v$。
• $1,1 = 1,0 + 0,1$，选同侧的 $u_0, v_0$ 或 $u_1, v_1$。
• $0,2 = 0,1 + 0,1$，选 $v_0, v_1$，不选 $u$。

在新图中连交叉边 $(u_0, v_1)$ 和 $(u_1, v_0)$ 得到二分图。原问题等价于求二分图的 MIS。

分层、拆点与建立虚点

【CF1941G】坐地铁，求从指定点开始，到任意一点的最少换乘次数。把线路也看做点，01 BFS。

【P4568】无向带权图。你可以选择图中最多 $K$ 条边，将其权值修改为 $0$。计算从指定起点 $S$ 到终点 $T$ 的最短路。$0 \leqslant K \leqslant 10$。建 $K+1$ 层图，每层图向下一层图的边权为 $0$。

【CF1473E】给定一个 $N$ 点 $M$ 无向边的图。一条路径的权值为 $\sum w_i-\max w_i+\min w_i$。求从 $1$ 号点到每个点的最短路。可以把路径的权值理解为：必须将路径上的任意一条边不算代价，任意一条边算 2 倍代价。这样我们就把对两条极值边的贡献方式转化成了所有边的贡献方式。更加统一，易于处理。这两种特殊代价没有先后顺序，故建 $4$ 层图：$1\to2$ 边权为 $0$，$2\to4$ 边权为 $2w$，$1\to3$ 边权为 $2w$，$3\to4$ 边权为 $0$。答案为第 $1$ 层与第 $4$ 层图对应的答案的较小值。

【CF2014E】无向带权图。在 $N$ 个顶点中，$H$ 个顶点各有一匹可用的马。骑马时，行进时间减半。甲从顶点 1 开始，乙从顶点 $N$ 开始。求甲和乙最早在某个顶点相遇的时间。

【2024 ICPC 网络赛 II E】走迷宫，从 1 走到 $N$。给定迷宫中有 $K$ 个杀手机器人，机器人通过的路径长度不能超过 $D$，但走过的路径可以撤销。每秒玩家与杀手机器人同时移动，两者始终不能相遇。问能否走到终点。奇偶分层，对于某个点，玩家到达步数是 $x$，机器人到达步数是 $y$，则如果 $x$ 与 $y$ 的奇偶性相同，且 $x \geqslant y$，这个点就不能经过。

CF1245D

• 给定 $N$ 个点，每个点 $i$ 有点权 $C_i$，任意两点 $i, j$ 之间有无向边权 $W_{i,j}$。
• 可以花费 $C_i$ 激活点 $i$，或者花费 $W_{i,j}$ 连接点 $i$ 和点 $j$。
• 求使得图上所有点都与激活点连通的最小总花费。

建立虚点，连接点 $i$ 的边权 $C_{i}$，求全图 MST。

ABC416E. Development

$N$ 个城市，$M$ 条双向道路，以及 $K$ 个机场。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，通行时间为 $C_i$。机场位于城市 $D_1,\ldots,D_K$，有机场的城市之间可以以 $T$ 时间互相到达。

$Q$ 个查询：

1. 在城市 $x$ 和城市 $y$ 之间新建一条双向道路，通行时间为 $t$。
2. 在城市 $x$ 新建一个机场。
3. 计算 $\sum_{x=1}^{N}\sum_{y=1}^{N}d(x,y)$。

建立虚点，连接机场的边权 $\dfrac{T}{2}$。查询时枚举中转点，复杂度 $\mathcal{O}(QN^{2})$。

二分图与基环树

给定一个二分图 $G = (U, V, E)$，其中：

1. 左部点集与右部点集大小相等，即 $|U| = |V| = N$。
2. 左部点中的任意顶点 $u \in U$，其度数恒为 2。
3. 图 $G$ 中允许存在重边（即一个 $u$ 可能与同一个 $v$ 连接两条边）。

求二分图 $G$ 中完美匹配的数量。

构建一个全新的图 $G'$：

• $G'$ 的点集为原图的右部点集 $V$（共 $N$ 个点）。
• $G'$ 的边集由原图的左部点集 $U$ 构成。由于每个 $u$ 都关联恰好两个右部点 $v_{1}$ 和 $v_{2}$，把 $u$ 看作是连接 $v_{1}$ 和 $v_{2}$ 的一条边（可能是自环）。

$G'$ 是基环树森林，完美匹配意味着为 $G'$ 中的边定向，使得每个点的入度恰好为 1。

对于每个连通块，若点数 = 边数，则无解。若连通块满足点数 = 边数，则贡献为 2。

例子：1770D