AtCoder UTPC2013_03 - 做题记录

原题链接

• AtCoder C - 直径

• 洛谷 AT838 直径

首先来理解题目的意思

• 输入两幅图 $G_{1}$ 与 $G_{2}$，分别拥有 $n_{1}$ 与 $n_{2}$ 个点，$m_{1}$ 与 $m_{2}$ 条边
• 要求在两图中间添加一条边使两图联通并求出所得到的新图的最大直径与最小直径

思路

存图

const int MAX_N = 1005;
class Edge {
 public:
  int from, to;
};
vector<Edge> G[MAX_N];

直径

定义

对于直径的定义为 : 图上任意两点的最短距离的最大值

以下方的图为例子：

各点到另外的点之间的最短距离为

1 \stackrel{1}{\rightleftharpoons} 2 \quad 1 \stackrel{2}{\rightleftharpoons} 3 \quad 1 \stackrel{1}{\rightleftharpoons} 4 \quad 1 \stackrel{2}{\rightleftharpoons} 5 \newline 2 \stackrel{1}{\rightleftharpoons} 3 \quad 2 \stackrel{1}{\rightleftharpoons} 4 \quad 2 \stackrel{2}{\rightleftharpoons} 5 \newline 3 \stackrel{2}{\rightleftharpoons} 4 \quad 3 \stackrel{1}{\rightleftharpoons} 5 \newline 4 \stackrel{1}{\rightleftharpoons} 5 \newline

则该图的直径为 $2$。

直径的求法

两遍 BFS

1. 先在图上随便选取一个点，对他进行 BFS 后，找到离它最远的点。（为了到达图的边缘）
2. 在最远的点上在进行一次 BFS ，此时它与离它最远的那个点之间的最短距离即为该图的直径。

例子：

1. 假设随机选取的点为 $5$，则进行 BFS 后选取的点为 $9$。
2. 再在 $9$ 进行一次 BFS ，得到的点为 $8$，那么该图的直径为 $9$ 到 $8$ 的距离 $6$。

代码（C++11）

void bfs(const int from = 1) { // 默认从1开始搜索
  queue<Edge> que;
  que.push(Edge{from, 0});  // 联赛中修改为 'que.push((Edge) {from, 0})'

  while (!que.empty()) {
    Edge now = que.front();
    que.pop();

    for (int i = 0; i < G[now.from].size(); ++i) {
      Edge edge = G[now.from][i];
      if (dis[edge.to] > dis[edge.from] + 1) {
        dis[edge.to] = dis[edge.from] + 1;
        que.push(Edge{edge.to, 0});  //联赛中修改为 'que.push((Edge) {edge.to, 0})'
      }
    }
  }
}

进行一次 BFS 之后再来一次即可

单源最短路

dijkstra

直接在图上每个点都跑一遍 dijkstra，再取最大值即可。代码相似于 BFS，由于每条边的权值都一样，这道题可不使用priority_queue

SPFA

它死了

求解

我们发现，对于添加一条边后新图的直径 $d_{G_{new}}$ 满足

$d_{G_{new}} \leq d_{G_{1}} + d_{G_{2}} + 1$

最长直径

则新图的最长直径为

$d_{G_{new} \ max} = d_{G_{1}} + d_{G_{2}} + 1$

最短直径

• 构建成的新图的最短直径必然大于 $d_{G_{1}}$ 与 $d_{G_{2}}$（样例 3）

• 而最短直径为 $G_{1}$ 与 $G_{2}$ 中最远两点之间距离（可在 BFS 或 dijkstra 时顺便求出）的最小值之和再加一

• $d_{G_{new} \ min} = max(min(G_{1} \ min, G_{2} \ min), \ max(d_{G_{1}}, d_{G_{2}}))$

综上，可 AC 此题。

蒟蒻第一次写题解，不足之处还请大家提出并谅解。