Giả sử ta có danh sách cạnh cây dạng [u, v], biểu thị cạnh vô hướng giữa u và v. Còn có hai giá trị x và y. Nếu ta ở nút x, đối thủ ở nút y. Vòng đầu ta di chuyển, vòng sau đối thủ di chuyển, luân phiên. Đối thủ có thể chọn không di chuyển trong một vòng. Ta phải tìm số vòng tối thiểu để bắt đối thủ.
Ví dụ: edges = [[0,1],[0,2],[1,3],[1,4]], x=0, y=3, đầu ra=3. Vòng 1: ta từ 0 đến 1. Vòng 2: đối thủ ở yên 3. Vòng 3: ta đến 3.
Để giải quyết, ta làm theo các bước:
- N := 1e5 + 5.
- Định nghĩa mảng visited và visited2 kích thước N, điền -1.
- Tạo danh sách kề graph cho N nút.
- for mỗi cạnh trong edges: thêm vào graph hai chiều.
- Định nghĩa hàng đợi q. Đưa u vào q, visited[u]=0.
- while q không rỗng: BFS từ u tính visited (khoảng cách từ u).
- Đưa v vào q, ret=0, visited2[v]=0.
- while q không rỗng:
- node = q.front(); q.pop().
- ret = max(ret, 2*visited[node] - 1).
- for each it trong graph[node]:
- Nếu visited2[it]==-1 và visited2[node]+2 < visited[it]: visited2[it]=visited2[node]+1; q.push(it).
- Trả về ret.
Xem triển khai dưới đây:
Ví dụ
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int visited[N]; int visited2[N]; vector<int> graph[N]; class Solution { public: int solve(vector<vector<int>>& edges, int u, int v) { memset(visited, -1, sizeof visited); memset(visited2, -1, sizeof visited2); for (int i = 0; i < N; i++) graph[i].clear(); for (auto& it : edges) { graph[it[0]].push_back(it[1]); graph[it[1]].push_back(it[0]); } queue<int> q; q.push(u); visited[u] = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (auto& it : graph[node]) { if (visited[it] == -1) { visited[it] = visited[node] + 1; q.push(it); } } } q.push(v); int ret = 0; visited2[v] = 0; while (!q.empty()) { int node = q.front(); q.pop(); ret = max(ret, 2 * (visited[node]) - 1); for (auto& it : graph[node]) { if (visited2[it] == -1 && visited2[node] + 2 < visited[it]) { visited2[it] = visited2[node] + 1; q.push(it); } } } return ret; } }; int solve(vector<vector<int>>& edges, int u, int v) { return (new Solution())->solve(edges, u, v); } int main(){ vector<vector<int>> edge = {{0, 1},{0, 2},{1, 3},{1, 4}}; int x = 0, y = 3; cout << solve(edge, x, y); }
Đầu vào
[ [0, 1], [0, 2], [1, 3], [1, 4] ], 0, 3
Đầu ra
3