作业四：图算法综合

本次作业的四道题分别对应带权二分判定、最大权独立集到最小割的转化、Kruskal，以及带资源次数的分层 Dijkstra。重点是识别隐藏在题面背后的标准图模型。

1. 关押罪犯：带权冲突与奇环

每对罪犯 $(u,v)$ 有冲突值 $w$ 。把人分进两个监狱，同一监狱中的冲突可能发生；目标最小化最大冲突值。

把冲突边按 $w$ 从大到小处理。对当前较大的边，我们希望两个端点必须分在不同监狱。只要这些“必须异侧”的约束仍能二染色，就能避免所有已处理冲突。

第一次加入某条权重为 $w$ 的约束后出现矛盾，说明更大的边都能避免，但无法同时避免这条边，答案就是 $w$ 。

parity[x] 表示 $x$ 与其并查集父结点是否在不同侧。路径压缩时异或累计关系。

合并约束“ $u$ 与 $v$ 异侧”时，若根不同，要设置根之间的奇偶关系为

parity[root_u]=parity[u]\oplus parity[v]\oplus1.

若根相同却发现 $parity[u]=parity[v]$ ，说明既有关系推出二者同侧，与新约束冲突；本质上形成了奇环。

排序 $O(M\log M)$ ，并查集近似 $O(M\alpha(N))$ 。

网格每格有非负权值，要求选若干互不相邻的格子，使权值和最大。棋盘按 $(i+j)$ 奇偶天然二分；相邻格一定属于不同侧。

“不能同时选择相邻格”说明被选顶点构成独立集。对任意图：

\text{最大权独立集}=\text{总权重}-\text{最小权顶点覆盖}.

二分图的最小权顶点覆盖可化为最小割：

有限割不能切断无穷边，所以每条相邻关系至少有一个端点被割掉，对应选择一个顶点进入覆盖。最小割容量就是最小覆盖权值。

由最大流最小割定理：

answer=\sum a_{ij}-maxflow.

提交程序使用 Dinic。INF 要大于所有格子权值总和，不能只是一个随手写的小常数。

对无向带权图，按边权升序枚举：若两个端点当前不在同一连通分量，就选边并合并。

每次选择的边都是连接两个已有分量的全局最轻候选，对相应割而言是安全边。选到 $N-1$ 条边即形成 MST。

提交程序正确使用路径压缩和按集合大小合并，复杂度 $O(M\log M)$ 。

程序最后直接输出累计权重。若图不连通，选中边数会少于 $N-1$ ，此时得到的是最小生成森林，不是生成树。若题目不保证连通，应检查 cnt == n - 1，否则按题意输出“不连通”标记。

从 1 到 $N$ ，最多可以让 $K$ 条道路免费，求最小花费。仅用 dist[u] 不够，因为到达同一顶点时，“已用几次免费机会”会影响未来选择。

定义状态

dist[u][k]=\text{到达 }u\text{ 且已免费升级 }k\text{ 条边的最小代价}.

经过边 $(u,v,w)$ 有两种转移：

dist[v][k]\leftarrow\min(dist[v][k],dist[u][k]+w);

dist[v][k+1]\leftarrow\min(dist[v][k+1],dist[u][k]).

这等价于建立 $K+1$ 层图：同层付费边权为 $w$ ，跨到下一层的免费边权为 0。所有边权非负，可以运行 Dijkstra。

答案是

\min_{0\le k\le K}dist[N][k],

因为允许“最多”使用 $K$ 次，而非必须恰好使用。复杂度约为

O((N+M)K\log(NK)).

同一个“图”字背后可能是完全不同的目标函数。先写清状态、约束和优化目标，再选择算法，远比看到关键词就套模板可靠。