Hướng dẫn cho LQDOJ CUP 2022 - Round 5 - NETWORK
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors: ,
Đọc hiểu đề
Nhắc lại: \(E\) là số cạnh cần dùng, \(L\) là khoảng cách lớn nhất giữa các cặp đỉnh \((x,y)\) liên thông với nhau trong cách nối.
Từ định nghĩa \(f = E \cdot n + L\) (lại có \(n > L\)), dễ thấy để \(f\) nhỏ nhất thì cần tìm cách dựng để \(E\) nhỏ nhất, nếu có nhiều cách cùng đạt được \(E\) nhỏ nhất thì chọn cách làm cho \(L\) nhỏ nhất.
Lưu ý
Đề bài có thể có yêu cầu u u. Khi đó các máy trong cùng trạm u cần liên lạc với nhau.
Tương tự, nếu có một đỉnh w không xuất hiện trong toàn bộ yêu cầu u v, thì các máy trong trạm \(w\) không cần liên lạc, và vì thế không cần nối (rất nhiều thí sinh bị sai trường hợp này)
Subtask \(1\) (\(30\%\) số điểm): \(n \le 6\).
Tutorial
Do \(n \leq 6\) nên số cạnh tối đa của đồ thị là \(C^2_n = \frac{n(n-1)}{2} \le 15\).
Để giải subtask này, ta có thể duyệt qua toàn bộ các cách chọn cạnh (duyệt tập con), và:
- Kiểm tra: máy trong trạm \(u\) có liên lạc được với máy trong trạm \(v\) không, có thỏa mãn ràng buộc về bậc \(c_i\) không;
- Tính \(L\): có thể dùng BFS.
Từ đó chọn ra cách tối ưu nhất.
Độ phức tạp: \(\displaystyle O\left(2^{C^2_n} \cdot (m+n)^2\right)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 25;
int numNodes, numGroups, numRequests;
vector <vector <int> > groups;
int capa[MAX_N];
bool required[MAX_N][MAX_N];
int from[MAX_N], to[MAX_N];
vector <int> adj[MAX_N];
int dist[MAX_N][MAX_N];
void bfsFrom(int u, int disU[]) {
for (int v = 1; v <= numNodes; v++) {
disU[v] = -1;
}
queue <int> bfs;
disU[u] = 0;
bfs.push(u);
while (!bfs.empty()) {
int v = bfs.front(); bfs.pop();
for (int w : adj[v]) {
if (disU[w] == -1) {
disU[w] = disU[v] + 1;
bfs.push(w);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NETWORK.inp", "r", stdin);
freopen("NETWORK.out", "w", stdout);
cin >> numNodes >> numGroups >> numRequests;
for (int i = 1; i <= numNodes; i++) {
cin >> capa[i];
}
groups.resize(numGroups);
for (int i = 0; i < numGroups; i++) {
int siz;
cin >> siz;
groups[i].resize(siz);
for (auto& id : groups[i]) {
cin >> id;
}
}
for (int u, v, i = 1; i <= numRequests; i++) {
cin >> u >> v;
for (auto x : groups[u-1]) for (auto y : groups[v-1]) {
required[x][y] = required[y][x] = true;
}
}
int numEdges = 0;
for (int x = 1; x <= numNodes; x++) {
for (int y = x+1; y <= numNodes; y++) {
from[numEdges] = x;
to[numEdges] = y;
numEdges++;
}
}
int f = 1e9, conf = -1;
for (int msk = 0; msk < (1<<numEdges); msk++) {
int E = __builtin_popcount(msk);
for (int u = 1; u <= numNodes; u++) {
adj[u].clear();
}
for (int i = 0; i < numEdges; i++) {
if (msk>>i&1) {
int u = from[i], v = to[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
}
bool ok = true;
for (int u = 1; u <= numNodes; u++) {
if (adj[u].size() > capa[u]) {
ok = false;
}
}
if (!ok) {
continue;
}
for (int u = 1; u <= numNodes; u++) {
bfsFrom(u, dist[u]);
}
int L = 0;
for (int x = 1; x <= numNodes && ok; x++) {
for (int y = x+1; y <= numNodes && ok; y++) {
if (required[x][y] and dist[x][y] == -1) {
ok = false;
}
L = max(L, dist[x][y]);
}
}
if (!ok) {
continue;
}
int cur_f = numNodes * E + L;
if (f > cur_f) {
f = cur_f;
conf = msk;
}
}
cout << f << '\n';
for (int i = 0; i < numEdges; i++) {
if (conf>>i&1) {
cout << from[i] << ' ' << to[i] << '\n';
}
}
return 0;
}
Subtask \(2\) (\(30\%\) số điểm): \(c_i = n \ \forall 1 \leq i \leq n\).
Tutorial
Nhận xét 1: Do mọi đỉnh đều có \(n\) cổng kết nối, mọi cách chọn cạnh đều thỏa mãn điều kiện về chặn trên của bậc mỗi đỉnh, vì thế có thể bỏ qua ràng buộc này.
Nhận xét 2: Giả sử trạm \(u\) cần truyền tin cho trạm \(v\), vậy thì trong đồ thị ta cần xây, mỗi đỉnh \(x \in u\) phải liên thông với mọi đỉnh \(y \in v\) (máy \(x\) thuộc trạm \(u\), máy \(y\) trạm \(v\)).
Để ý rằng các yêu cầu là có hướng, nhưng kết nối giữa các máy là vô hướng nên ta có tính chất như trên.
Như vậy, có thể coi các yêu cầu như cạnh hai chiều. Xét các thành phần liên thông (TPLT) được tạo nên từ các trạm và các yêu cầu. Dễ thấy, để \(E\) đạt \(\min\) thì cần dựng cây khung cho mỗi TPLT.
Nhận xét 3: Với một TPLT - tập đỉnh \(V\) cho trước, có thể chọn một đỉnh \(u\) bất kì làm trung tâm, \(|V|-1\) đỉnh còn lại sẽ nối vào \(u\). Cách làm trên sẽ cho ra đồ thị có khoảng cách lớn nhất giữa hai đỉnh bất kì luôn \(\le 2\). Cấu hình này được gọi là mạng hình sao (bạn có thể tìm từ khóa "star topology" và "network topology").
Với các nhận xét trên, ta có cách giải cho subtask này như sau:
- Xác định các thành phần liên thông (bằng DFS/BFS hoặc DSU)
- Với mỗi TPLT, từ danh sách các đỉnh thuộc TPLT này, bạn in ra các cạnh để tạo đồ thị (cây) có dạng nêu trên.
Độ phức tạp: \(O(n + m)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 2;
int numNodes, numGroups, numEdges;
vector <vector <int> > groups;
int capa[MAX_N];
vector <int> adj[MAX_N];
int cid[MAX_N];
vector <int> comp[MAX_N];
void dfs(int u, int id) {
if (cid[u]) {
return;
}
cid[u] = id;
for (auto v : adj[u]) {
dfs(v,id);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NETWORK.inp", "r", stdin);
freopen("NETWORK.out", "w", stdout);
cin >> numNodes >> numGroups >> numEdges;
for (int i = 1; i <= numNodes; i++) {
cin >> capa[i];
}
groups.resize(numGroups);
for (int i = 0; i < numGroups; i++) {
int siz;
cin >> siz;
groups[i].resize(siz);
for (auto& id : groups[i]) {
cin >> id;
}
}
for (int u, v, i = 1; i <= numEdges; i++) {
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int numComps = 0;
for (int u = 0; u < numGroups; u++) {
if (!adj[u].empty()) {
dfs(u,++numComps);
}
}
for (int u = 0; u < numGroups; u++) {
for (auto id : groups[u]) {
comp[cid[u]].push_back(id);
}
}
int delay = 0;
vector <pair <int, int> > edges;
for (int t = 1; t <= numComps; t++) {
if (comp[t].empty()) {
continue;
}
for (int i = 1; i < comp[t].size(); i++) {
edges.push_back({comp[t][0], comp[t][i]});
}
delay = max(delay, comp[t].size() > 2 ? 2 : 1);
}
numEdges = edges.size();
long long f = 1ll * numEdges * numNodes + delay;
cout << f << '\n';
for (auto x : edges) {
cout << x.first << ' ' << x.second << '\n';
}
return 0;
}
Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Với giới hạn số cổng, ta không thể kết nối một cách tùy ý. Mở rộng ý tưởng của subtask 2, ta có thể tạo đồ thị có cấu hình 'tương tự' để đạt được độ trễ nhỏ nhất.
Thuật toán: Đầu tiên, chọn đỉnh có \(c_i\) lớn nhất làm gốc cây. Tại mỗi bước, chọn đỉnh \(v\) chưa thuộc cây có \(c_v\) lớn nhất và nối vào một đỉnh \(u\) thuộc cây, \(u\) có độ sâu thấp nhất có thể (và số cạnh nối vào \(u\) hiện tại vẫn \(<c_u\)). Lặp lại cho tới khi toàn bộ đỉnh trong TPLT đều thuộc cây.
Cụ thể, mã giả cho cách làm này như sau:
sắp xếp các đỉnh theo c_i giảm dần
duyệt các đỉnh u trong TPLT theo thứ tự
gọi t = min(số đỉnh chưa được nối, số kết nối còn lại của u)
nối vào u: t đỉnh có c_i lớn nhất, chưa được nối.
Vì ưu tiên nối đỉnh theo độ sâu tăng dần, ta có thể hình dung quá trình thêm đỉnh giống thuật toán BFS.
Để độ sâu của cây thấp nhất có thể, ta sắp các đỉnh theo thứ tự giảm dần về bậc (\(c_i\)).
Việc tính độ trễ chính là bài toán "Tìm đường kính của cây".
Độ phức tạp: \(O((n+m) \log n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 2;
int numNodes, numGroups, numEdges;
vector <vector <int> > groups;
int capa[MAX_N];
bool cmp(int i, int j) {
return capa[i] > capa[j];
}
vector<int> adj[MAX_N];
int cid[MAX_N];
vector<int> comp[MAX_N];
void dfs(int u, int id) {
if (cid[u]) {
return;
}
cid[u] = id;
for (auto v : adj[u]) {
dfs(v,id);
}
}
pair <int, int> findFurthest(int u, int pa) {
pair <int,int> res(-1,u);
for (auto v : adj[u]) {
if (v != pa) {
res = max(res, findFurthest(v,u));
}
}
++res.first;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("NETWORK.inp", "r", stdin);
freopen("NETWORK.out", "w", stdout);
cin >> numNodes >> numGroups >> numEdges;
for (int i = 1; i <= numNodes; i++) {
cin >> capa[i];
}
groups.resize(numGroups);
for (int i = 0; i < numGroups; i++) {
int siz;
cin >> siz;
groups[i].resize(siz);
for (auto& id : groups[i]) {
cin >> id;
}
}
for (int u, v, i = 1; i <= numEdges; i++) {
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int numComps = 0;
for (int u = 0; u < numGroups; u++) {
if (!adj[u].empty()) {
dfs(u,++numComps);
}
}
for (int u = 0; u < numGroups; u++) {
for (auto id : groups[u]) {
comp[cid[u]].push_back(id);
}
}
for (int i = 1; i <= numNodes; i++) {
adj[i].clear();
}
numEdges = 0;
int delay = 0;
vector <pair <int, int> > edges;
for (int t = 1; t <= numComps; t++) {
if (comp[t].empty()) {
continue;
}
sort(comp[t].begin(), comp[t].end(), cmp);
int sz = comp[t].size();
for (int j = 1, i = 0; i < sz && j < sz; i++) {
int u = comp[t][i];
int k = min(sz, j+capa[u])-1;
for (; j <= k; j++) {
int v = comp[t][j];
edges.push_back({u,v});
adj[u].push_back(v);
adj[v].push_back(u);
--capa[v];
}
j = k+1;
}
int u = comp[t][0];
u = findFurthest(u,u).second;
delay = max(delay, findFurthest(u,u).first);
}
numEdges = edges.size();
long long f = 1ll * numEdges * numNodes + delay;
cout << f << '\n';
for (auto x : edges) {
cout << x.first << ' ' << x.second << '\n';
}
return 0;
}
Bình luận (1)