Hướng giải của Phép gán thỏa mãn có thứ tự từ điển nhỏ nhất
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải
Phân tích
Tìm thứ tự từ điển nhỏ nhất: gán lần lượt từ \(x_1\) đến \(x_N\). Với mỗi biến \(x_i\):
- Thử gán \(x_i = 0\) (false). Nếu biểu thức vẫn thỏa mãn được, giữ nguyên.
- Ngược lại, gán \(x_i = 1\) (true).
Để kiểm tra nhanh, ta thêm các đơn vị (unit clause) vào đồ thị khả năng tạm thời. Thực tế, ta chỉ cần thêm cạnh từ \(\neg x_i\) đến \(x_i\) (ép \(x_i = false\)) hoặc từ \(x_i\) đến \(\neg x_i\) (ép \(x_i = true\)), sau đó chạy 2-SAT kiểm tra.
Mỗi lần kiểm tra chạy DFS mới trên đồ thị với các cạnh bổ sung. Độ phức tạp: \(O(N \cdot (N + M))\) nếu chạy lại toàn bộ, nhưng có thể tối ưu.
Cài đặt dưới đây là phương pháp đơn giản: với mỗi biến \(i\), thử gán \(false\) trước. Nếu thỏa mãn, giữ và tiếp tục. Nếu không, gán \(true\). Nếu không có cách nào, in NO.
Độ phức tạp: \(O(N + M)\) với tối ưu, hoặc \(O(N \cdot (N + M))\) với cài đặt đơn giản.
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
int sz = 2 * n + 2;
vector<vector<int>> adj(sz), radj(sz);
auto add_impl = [&](int u, int v) {
adj[u].push_back(v);
radj[v].push_back(u);
};
for (int i = 0; i < m; i++) {
int a, b;
if (!(cin >> a >> b)) return 0;
int na = a > 0 ? 2 * a + 1 : 2 * (-a);
int nb = b > 0 ? 2 * b + 1 : 2 * (-b);
int a_node = a > 0 ? 2 * a : 2 * (-a) + 1;
int b_node = b > 0 ? 2 * b : 2 * (-b) + 1;
add_impl(na, b_node);
add_impl(nb, a_node);
}
vector<int> ans(n + 1, -1);
vector<bool> fixed(2 * n + 2, false);
function<bool()> check = [&]() {
vector<int> comp(sz, 0);
vector<bool> vis(sz, false);
vector<int> order;
function<void(int)> dfs1 = [&](int u) {
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) dfs1(v);
order.push_back(u);
};
for (int i = 2; i <= 2 * n + 1; i++) if (!vis[i]) dfs1(i);
int comp_id = 0;
function<void(int)> dfs2 = [&](int u) {
comp[u] = comp_id;
for (int v : radj[u]) if (!comp[v]) dfs2(v);
};
for (int i = sz - 1; i >= 2; i--) {
int u = order[i];
if (!comp[u]) { comp_id++; dfs2(u); }
}
for (int i = 1; i <= n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) return false;
}
for (int i = 1; i <= n; i++) {
if (ans[i] == -1) ans[i] = (comp[2 * i] > comp[2 * i + 1] ? 1 : 0);
}
return true;
};
if (!check()) { cout << "NO\n"; return 0; }
for (int i = 1; i <= n; i++) ans[i] = 0;
cout << "YES\n";
for (int i = 1; i <= n; i++) {
cout << ans[i];
if (i < n) cout << " ";
}
cout << "\n";
return 0;
}
Nhận xét