图论建模 | 小明の雜貨屋

ABC461G - Graph Problem 2026

$N$ 頂点 $M$ 辺の単純無向グラフ。

$0 \leqslant W_j \leqslant 2$ 。
各辺 $i$ について、 $W_{u_i}+W_{v_i} \leqslant 2$

$\sum_{j=1}^{N}{W_j}$ の最大値を求めてください。

边的分配无非是 2,0 或 1,1。拆分：

2,0 = 1,0 + 1,0
1,1 = 1,0 + 0,1
0,2 = 0,1 + 0,1

于是问题化为两张 01 的图，求二分图的 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$ 个查询：

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

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

二分图与基环树

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

左部点集与右部点集大小相等，即 $|U| = |V| = N$ 。
左部点中的任意顶点 $u \in U$ ，其度数恒为 2。
图 $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