跳转至

小团无路可逃#
发布于2021-04-16
上次编辑2021-04-16

问题描述#

小团惹小美生气了，小美要去找小团“讲道理”。小团望风而逃，他们住的地方可以抽象成一棵有n个结点的树，小美位于 x 位置，小团位于 y 位置。小团和小美每个单位时间内都可以选择不动或者向相邻的位置转移，很显然最终小团会无路可逃，只能延缓一下被“讲道理”的时间，请问最多经过多少个单位时间后，小团会被追上。

格式：

输入：
- 输入第一行包含三个整数 n，x，y，分别表示树上的结点数量，小美所在的位置和小团所在的位置。
- 接下来有 n-1 行，每行两个整数 u，v，表示 u 号位置和 v 号位置之间有一条边，即 u 号位置和 v 号位置彼此相邻。
输出：
- 输出仅包含一个整数，表示小美追上小团所需的时间。

示例：

输入：
     5 1 2
     2 1
     3 1
     4 2
     5 3
输出：2

提示：

  • 1 <= n <= 50000

解题思路#

方法一：BFS#

\(x\) 先走，走过的位置 \(y\) 不能再走。

如果 \(x\) 走到某个位置时，该位置 \(y\) 已经走过，则更新最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys
from collections import deque
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


n, x, y = readints()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = readints()
    adj[u].append(v)
    adj[v].append(u)
qx, qy = deque([x]), deque([y])
vx, vy = [False] * (n + 1), [False] * (n + 1)
vx[x] = vy[y] = True
ans, step = 0, 1
while qx:
    m = len(qx)
    for _ in range(m):
        u = qx.popleft()
        for v in adj[u]:
            if not vx[v]:
                vx[v] = True
                qx.append(v)
                if vy[v]:
                    ans = max(ans, step)
    m = len(qy)
    for _ in range(m):
        u = qy.popleft()
        for v in adj[u]:
            if not vx[v] and not vy[v]:
                vy[v] = True
                qy.append(v)
    step += 1
print(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, x, y;
    cin >> n >> x >> y;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<int> vx(n + 1), vy(n + 1);
    queue<int> qx, qy;
    vx[x] = vy[y] = 1;
    qx.emplace(x), qy.emplace(y);
    int ans = 0, step = 1;
    while (!qx.empty()) {
        int m = qx.size();
        while (m--) {
            int u = qx.front();
            qx.pop();
            for (int v : adj[u]) {
                if (!vx[v]) {
                    vx[v] = 1;
                    if (vy[v]) {
                        ans = max(ans, step);
                    }
                    qx.emplace(v);
                }
            }
        }
        m = qy.size();
        while (m--) {
            int u = qy.front();
            qy.pop();
            for (int v : adj[u]) {
                if (!vx[v] && !vy[v]) {
                    vy[v] = 1;
                    qy.emplace(v);
                }
            }
        }
        ++step;
    }
    cout << ans << '\n';
    return 0;
}
返回顶部

在手机上阅读