UVA1439 独占访问2 Exclusive Access 2 题解

首先理解题意，给出无向图，给每一条边定向成为有向无环图，使得最长路的长度最短，这里的最长路长度指最长路上点的个数。如果令 $dis_i$ 表示以 $i$ 号点结尾的最长路的长度，那么最后答案应该为 $\max(dis_i)$。

首先观察性质，如果 $dis_i = dis_j$，那么证明 $i$ 和 $j$ 之间没有直接的边，因为根据最长路转移的不等式可知如果设从 $i$ 到 $j$ 有一条边，那么 $dis_j \ge dis_i + 1$，不符合 $dis_i = dis_j$，所以不存在从 $i$ 到 $j$ 的边；反之同理。

那么当我们定向完成之后，可以求出对于任意点 $i$ 的 $dis_i$，那么我们根据 $dis_i$ 的值分层，值相同的分为一层，那么根据上述性质可知，每层点内部无边。为了让最长路最短，那么应该在上述条件下，使得层数最少。

形式化的讲：原问题为找到无向图 $G$ 的一个定向 $D$，使得 $|D|$ 的值最小，其中 $|D|$ 表示 $D$ 中最长路径的包含的点数，即本题中的长度；新问题为找到 $V$ 的一个分层 $K$，即把点分为若干个集合，并且每个集合内部无边，使得 $|K|$ 最少，其中 $|K|$ 表示分层的个数。原问题与新问题可证明完全等价。

首先证明，如果 $G$ 有一个定向 $D$，那么存在 $V$ 的一个分层 $K$，使得 $|D| = |K|$，其中运算与上文描述相同。因为 $|D| = \max(dis_i)$，$dis_i$ 表示为以 $i$ 结尾的最长路所包含的点数，即本题中的长度。由上文证明可得 $i$ 与 $j$ 之间无边与 $dis_i = dis_j$ 等价。那么假设已经确定了一个 $G$ 的定向 $D$，可以求出对于任意一个点 $i$ 的 $dis_i$，把所有 $dis_i = k$ 的点 $i$ 放到第 $k$ 个集合中，其中 $k \in [1,|D|]$，因为每一个集合中互相无边，那么即构成了一个分层 $K$，且分到的层数 $|K|$，即集合个数，刚好为 $|D|$。

其次证明，如果 $V$ 有一个分层 $K$，那么存在 $G$ 的一个定向 $K$，使得 $|K| \ge |D|$，其中运算与上文描述相同。假设存在一个 $V$ 的分层 $K$，每一层内部都是没有边的且每一层之间存在边，假设把每一层按照不同的 $dis$ 从小到大排序，那么假设两个点 $i$ 和 $j$ 分别位于不同的层且 $i$ 比 $j$ 更靠左，将所有的边向右连，那么最长路在每一层最多选一个点，因此 $|D| = \max(dis_i) \le |K|$。

最后综合上述证明，假设 $K$ 是最小的分层，那么根据上述结论可以推出，存在一个 $G$ 的定向 $D$，使得 $|D| \le |K|$。另一方面，$|D|$ 不可能小于 $|K|$，因为如果 $|D| < |K|$，那么根据上述结论可以推出，存在分层 $K'$ 使得 $|K'| = |D|$，那么 $|K'| < |K|$，与 $K$ 为最小的分层这个条件相悖，所以 $|D| = |K|$。

那么问题变成了把点集分成若干个子集，每个子集内部无边，为独立集，显然可以状压动态规划。