Ý tưởng chính:
Mỗi truy vấn yêu cầu tô màu các đỉnh nằm trong khoảng cách ≤ d từ đỉnh u bằng màu c.
Truy vấn nào được xử lý sau sẽ có ưu tiên thấp hơn, nên cần xử lý ngược lại thứ tự nhập vào.
Chi tiết thuật toán:
Nhập dữ liệu đồ thị và truy vấn.
Đảo ngược danh sách truy vấn, vì truy vấn sau cùng phải được xử lý trước để màu của truy vấn đầu tiên được ưu tiên.
Với mỗi truy vấn (u, d, c):
Chạy BFS từ đỉnh u, trong phạm vi độ sâu d.
Nếu một đỉnh chưa được tô màu, thì tô màu nó.
Nếu đỉnh đã được tô nhưng bán kính hiện tại lớn hơn, thì tiếp tục cập nhật.
Tối ưu hóa:
Sử dụng mảng r[] để theo dõi bán kính xa nhất mà đỉnh đã được tô.
Tránh tô lại các đỉnh đã tô từ truy vấn trước (ưu tiên cao hơn).
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m, q;
vector<vector<int>> g(N);
vector<int> r(N, 0), vis(N), col(N);
struct var {
int u, d, c;
};
vector<var> a;
void bfs(int p, int d, int c) {
queue<int> q;
q.push(p);
if (!vis[p])
col[p] = c;
vis[p] = 1;
r[p] = d;
while (!q.empty()) {
int u = q.front();
q.pop();
if (r[u] > 0) {
for (auto& v : g[u]) {
if (vis[v] == 0) {
q.push(v);
vis[v] = 1, r[v] = r[u] - 1, col[v] = c;
} else {
if (r[u] - 1 > r[v]) {
q.push(v);
r[v] = r[u] - 1;
}
}
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> q;
for (int i = 1; i <= q; ++i) {
int u, d, c;
cin >> u >> d >> c;
a.push_back({u, d, c});
}
reverse(a.begin(), a.end());
for (auto& [u, d, c] : a)
bfs(u, d, c);
for (int i = 1; i <= n; ++i)
cout << col[i] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
Độ phức tạp: O(q * (n + m)).
duongnam
Created at
0 likes