题目理解

我们有一个无向图 $G$，包含 $n$ 个顶点和 $m$ 条边，需要给每个顶点分配一个观点值 $x_v \in [1,k]$，满足：

• 对于每条边 $(u,v)$，有 $|x_u - x_v| = 1$
• 持有极端观点（$1$ 或 $k$）的顶点数尽可能多

问题转化

条件分析

条件 $|x_u - x_v| = 1$ 意味着：

• 图必须是二分图（否则存在奇数环时无法满足）
• 观点值可以看作在图上的一种"层号"分配

二分图结构

如果图是二分图，我们可以将顶点分为两个集合 $A$ 和 $B$，使得：

• 相邻顶点属于不同集合
• 如果 $u \in A$ 且 $v \in B$ 相邻，则 $|x_u - x_v| = 1$

算法思路

$k$ 为奇数的情况

当 $k$ 为奇数时，采用简单策略：

• 在每个连通分量中，选择较大的那个集合分配观点 $1$（极端观点）
• 另一个集合分配观点 $2$
• 极端观点数为较大的集合大小

$k$ 为偶数的情况

这是更复杂的情况，采用以下步骤：

1. 构建冲突图：

   • 对于 $A$ 中的顶点 $a$ 和 $B$ 中的顶点 $b$
   • 如果它们之间的最短距离 $f[a][b] < k-1$，则在 $a$ 和 $b$ 之间连边
   • 这是因为如果距离太近，可能无法同时给它们分配极端观点

2. 二分图匹配：

   • 在冲突图上求最大匹配 $M$
   • 匹配数 $M$ 表示必须放弃的极端观点对数
   • 最终极端观点数为 $n - M$

3. 观点分配：

   • 通过构建残量网络和 BFS 标记
   • 确定哪些顶点应该获得极端观点
   • 使用 BFS 距离来分配具体的观点值

关键公式

极端观点数计算

对于 $k$ 为偶数的情况：

$$\text{极端观点数} = n - M$$

其中 $M$ 是冲突图的最大匹配数。

观点值分配

通过 BFS 距离 $d[v]$ 计算最终观点值：

$$x_v = \begin{cases} d[v] & \text{如果 } d[v] \leq k \\ k - ((d[v] - k) \bmod 2) & \text{否则} \end{cases} $$

代码中的实现

核心步骤

1. Floyd-Warshall：计算所有点对最短路径 $f[i][j]$
2. 二分图检测：DFS 染色验证图是否为二分图
3. 冲突图构建：对于 $A$ 中的 $a$ 和 $B$ 中的 $b$，如果 $f[a][b] < k-1$ 则连边
4. 匈牙利算法：在冲突图上求最大匹配
5. 残量网络分析：确定最终哪些顶点获得极端观点
6. BFS 距离分配：根据标记结果分配具体的观点值

时间复杂度

• Floyd-Warshall: $O(n^3)$，由于 $n \leq 200$，可行
• 二分图匹配: $O(nm)$
• 总体复杂度在给定数据范围内可接受

算法正确性

该算法基于以下保证：

1. 如果不是二分图，直接输出 NIE
2. $k$ 为奇数时，简单分配策略是最优的
3. $k$ 为偶数时，通过冲突图匹配找到必须放弃的极端观点对是最优的
4. 最终的 BFS 距离分配确保满足相邻顶点观点差为 $1$

算法标签

• 图论
• 二分图
• 最大匹配
• 最短路径
• BFS/DFS

代码总结

代码的核心是：

1. 二分图检测和染色
2. 根据 $k$ 的奇偶性采用不同策略
3. $k$ 为偶数时使用冲突图匹配来最大化极端观点数
4. 通过 BFS 距离分配确保观点值满足相邻差为 $1$ 的条件

这种方法能够在多项式时间内解决问题，并找到持有极端观点数最大的合法分配。