Tác giả:
Reviewer:
Trước khi đọc bài viết này, bạn cần trang bị kiến thức về các chủ đề sau:
Để hiểu rõ các kí hiệu và định nghĩa được sử dụng trong bài viết, chúng ta sẽ cùng tìm hiểu một số vấn đề sau:
Mệnh đề hay mệnh đề logic được định nghĩa là một câu khẳng định về một vấn đề nào đó. Một mệnh đề có thể là đúng [, ] hoặc sai [, ], không thể vừa đúng, vừa sai.
Ví dụ:
Mệnh đề phủ định của mệnh đề được định nghĩa là mệnh đề có giá trị đối lập với mệnh đề , kí hiệu .
Kí hiệu phép hội của mệnh đề là .
Mệnh đề sẽ đúng nếu đều đúng, và sai trong các trường hợp còn lại.
Kí hiệu phép tuyển của mệnh đề là .
Mệnh đề sẽ sai nếu đều sai, và đúng trong các trường hợp còn lại.
Kí hiệu " kéo theo " là .
Mệnh đề sẽ sai nếu đúng và sai, và đúng trong các trường hợp còn lại.
Kí hiệu " tương đương " là .
Mệnh đề sẽ đúng nếu đều đúng hoặc đều sai, và sai trong các trường hợp còn lại.
Dạng chuẩn hội (CNF) hay Conjunctive Normal Form là hội () của một hoặc nhiều mệnh đề. Các mệnh đề này có dạng là tuyển () của các giá trị ().
Ví dụ:
SAT hay Boolean satisfiability problem là một bài toán kiểm tra tồn tại cách gán cho một tập giá trị, sao cho thoả mãn CNF cho trước.
Ví dụ:
Bài Toán SAT là một bài toán thuộc lớp NP-complete. Hiện tại chưa có bất cứ thuật toán hiệu quả nào để giải quyết bài toán SAT.
1. Ít nhất một giá trị là :
2. 2 giá trị trái dấu:
3. 2 giá trị cùng dấu:
4. Bắt buộc một giá trị mang giá trị :
5. Bắt buộc một giá trị mang giá trị :
Bài toán 2-SAT là một nhánh nhỏ của bài toán SAT, với sự khác biệt nằm ở các mệnh đề của CNF khi lúc này có chính xác giá trị (2-CNF).
Nhờ ràng buộc này, ta có thể giải quyết bài toán trong thời gian đa thức. Cụ thể hơn, ta sẽ đi vào bài toán 2-SAT:
Ta sẽ xây dựng đồ thị có hướng với các cung là các mệnh đề chứa phép kéo theo, và các đỉnh là các giá trị.
Xét một mệnh đề bất kỳ:
Theo quy tắc suy luận, ta biết rằng, . Như vậy, ta sẽ thêm cung vào đồ thị.
Ngoài ra, ta cũng phải thêm cung vào đồ thị:
Viết lại bài toán sau khi xây dựng đồ thị:
Cho đồ thị , trong đó:
Tìm cách gán cho tập các đỉnh sao cho thoả mãn điều kiện:
Nhận xét: Các đỉnh cùng thuộc TPLTM phải mang cùng giá trị.
Để chứng minh, ta cần có các nhận định sau:
Khi thì ta có .
Khi thì ta có .
Do đó, với các đỉnh cùng thuộc TPLTM phải mang cùng giá trị .
Với nhận xét trên, trước tiên ta sử dụng thuật toán tìm TPLTM như Kosaraju hay Tarjan. Tuy nhiên trong bài viết, ta sẽ chỉ bàn tới thuật toán Tarjan. Sau đó, ta sẽ coi mỗi TPLTM như một đỉnh, từ đó thu được một đồ thị có hướng không chu trình (DAG).
Sau khi thực hiện thuật toán Tarjan, ta sẽ xác định được mảng Vị trí của trong thứ tự Tô-pô ngược bất kỳ (Đối với thuật toán Kosaraju, mảng là vị trí trong thứ tự Tô-pô xuôi bất kỳ):
Với mỗi giá trị , ta xét:
Trước khi chứng minh tính đúng đắn của thuật toán, ta cần chứng minh bổ đề sau:
Chứng minh bổ đề: Do ta có đường đi . Mặt khác, theo cách xây dựng đồ thị ta biết rằng nếu có cung thì sẽ có cung . Nên từ đường đi trên ta suy ra có đường đi , vậy nên .
Ta sẽ chứng minh các đỉnh của đồ thị được gán giá trị theo thuật toán nêu trên sẽ thoả mãn điều kiện của bài toán.
Chứng minh điều kiện 1: Nếu và cùng thuộc TPLTM thì bài toán vô nghiệm.
Dễ dàng nhận thấy nếu và cùng thuộc TPLTM thì và phải mang cùng giá trị, mâu thuẫn với điều kiện 1 của bài toán. Ta nói bài toán vô nghiệm.
Chứng minh điều kiện 2: Nếu và thì .
Ta sẽ chứng minh bằng phản chứng, giả sử tồn tại và mà :
Nếu và thì .
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500500;
int n, m;
// Lưu đồ thị G
vector<int> G[maxN << 1];
// Lấy giá trị phủ định của x
int NOT(int x) {
return x + (x <= n ? n : -n); // -x
}
// Thêm điều kiện u OR v
void add_clause(int u, int v) {
G[NOT(u)].push_back(v); // -u -> v
G[NOT(v)].push_back(u); // -v -> u
}
// Tìm thành phần liên thông mạnh
int id[maxN << 1];
int num[maxN << 1], low[maxN << 1];
int timeDFS = 0, scc = 0;
int st[maxN << 1];
void dfs(int u) {
num[u] = low[u] = ++timeDFS;
st[++st[0]] = u;
for(const int& v : G[u]) {
if(id[v] != 0) continue;
if(num[v] == 0) {
dfs(v);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
if(num[u] == low[u]) {
for(++scc; true; ) {
int v = st[st[0]--];
id[v] = scc;
if(v == u) break;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
add_clause(u, v);
}
// Thuật toán Tarjan
for(int i = 1; i <= 2 * n; ++i) {
if(!id[i]) dfs(i);
}
bool answer = 1;
for(int i = 1; i <= n; ++i) {
// Kiểm tra điều kiện tồn tại phương án
if(id[i] == id[NOT(i)]) answer = 0;
}
if(!answer) {
cout << "IMPOSSIBLE"; // Thông báo bài toán vô nghiệm
return 0;
}
// In tập giá trị a1, a2, ..., an
for(int i = 1; i <= n; ++i) cout << (id[i] < id[NOT(i)]) << " ";
return 0;
}
Độ phức tạp để thực hiện thuật toán Tarjan cũng như cả bài toán là
Cho số là độ dài dãy nhị phân và tính chất . Mỗi tính chất có dạng với ý nghĩa:
Một tính chất gọi là được thoả mãn nếu ít nhất hai trong ba điều kiện trên là đúng.
In ra nếu không tồn tại dãy nhị phân thoả mãn được tất cả tính chất. Ngược lại, In ra một dãy nhị phân thoả mãn.
Với mỗi tính chất:
Sử dụng thuật toán 2-SAT, ta giải quyết bài toán trong .
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100100;
int n, q;
vector<int> G[maxN << 1];
int NOT(int x) {
return x + (x <= n ? n : -n);
}
void add_clause(int u, int v) {
G[NOT(u)].push_back(v);
G[NOT(v)].push_back(u);
}
int id[maxN << 1];
int num[maxN << 1], low[maxN << 1];
int timeDFS = 0, scc = 0;
int st[maxN << 1];
void dfs(int u) {
num[u] = low[u] = ++timeDFS;
st[++st[0]] = u;
for(const int& v : G[u]) {
if(id[v] != 0) continue;
if(num[v] == 0) {
dfs(v);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
if(num[u] == low[u]) {
for(++scc; true; ) {
int v = st[st[0]--];
id[v] = scc;
if(v == u) break;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
if(ifstream("recruit.inp")) {
freopen("recruit.inp", "r", stdin);
freopen("recruit.out", "w", stdout);
}
cin >> n >> q;
for(int i = 1; i <= q; ++i) {
vector<int> val;
for(int j = 0; j < 3; ++j) {
int u, v; cin >> u >> v;
if(v == 0) u = NOT(u);
val.push_back(u);
}
add_clause(val[0], val[1]);
add_clause(val[0], val[2]);
add_clause(val[1], val[2]);
}
for(int i = 1; i <= 2 * n; ++i) {
if(!id[i]) dfs(i);
}
bool answer = 1;
for(int i = 1; i <= n; ++i) {
if(id[i] == id[NOT(i)]) answer = 0;
}
if(!answer) {
cout << "-1";
return 0;
}
for(int i = 1; i <= n; ++i) cout << (id[i] < id[NOT(i)]);
return 0;
}
Trong tình trạng đói nghèo, người dân khổ cực trăm bề. Nhận thức được điều đó, các Đảng trong nước quyết định họp bàn nhau lại, bỏ qua hiềm khích để xây dựng lại đất nước. Việc đầu tiên sẽ là họp để chọn ra các vị đại biểu để lập nên Quốc Hội. Mỗi Đảng đề cử một ứng viên để ứng cử Quốc Hội và hiện tại mỗi Đảng đều có gương mặt tiêu biểu nhất để ứng cử vị trí đó. Tuy nhiên vì lý do cá nhân trong chiến tranh nên rất căm thù nhau (ví dụ như là ông của Đảng ghét ông của Đảng ...). Để đảm bảo Quốc Hội làm việc cách công minh thì các vị đại biểu Quốc Hội phải được chọn ra sao cho đảm bảo không có ai thù ghét ai cả nếu không rất có thể chiến tranh sẽ lại nổ ra. Bạn hãy xem xét xem liệu có cách tổ chức Quốc Hội sao cho thoả mãn được các yêu cầu đề ra hay không?
Dòng 1: 2 số nguyên và tương ứng là số Đảng và só mối quan hệ thù ghét nhau giữa các thành viên của các Đảng. (Các thành viên của Đảng có số hiệu là ; các thành viên của Đảng có số hiệu là ... Thành viên của Đảng sẽ có số hiệu là và ).
dòng tiếp theo mỗi dòng gồm số nguyên cho biết người và người ghét nhau. .
Dòng 1: Ghi nếu không có phương án thoả mãn và nếu có phương án thoả mãn.
Nếu dòng 1 là thì dòng thứ 2 ghi ra số nguyên là số hiệu của các thành viên được chọn vào Quốc Hội.
Với mỗi mối quan hệ thù ghét :
Với đại diện của mỗi Đảng:
Sử dụng thuật toán 2-SAT, ta giải quyết bài toán trong
#include <bits/stdc++.h>
using namespace std;
const int maxN = 16004;
int n, m;
vector<int> G[maxN << 1];
int NOT(int x) {
return x + (x <= n ? n : -n);
}
void add_clause(int u, int v) {
G[NOT(u)].push_back(v);
G[NOT(v)].push_back(u);
}
int id[maxN << 1];
int num[maxN << 1], low[maxN << 1];
int timeDFS = 0, scc = 0;
int st[maxN << 1];
void dfs(int u) {
num[u] = low[u] = ++timeDFS;
st[++st[0]] = u;
for(const int& v : G[u]) {
if(id[v] != 0) continue;
if(num[v] == 0) {
dfs(v);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
if(num[u] == low[u]) {
for(++scc; true; ) {
int v = st[st[0]--];
id[v] = scc;
if(v == u) break;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
n = n << 1;
for(int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
add_clause(NOT(u), NOT(v));
}
for(int i = 1; i <= n; i += 2) {
add_clause(i, i + 1);
add_clause(NOT(i), NOT(i + 1));
}
for(int i = 1; i <= 2 * n; ++i) {
if(!id[i]) dfs(i);
}
bool answer = 1;
for(int i = 1; i <= n; ++i) {
if(id[i] == id[NOT(i)]) answer = 0;
}
if(!answer) {
cout << "0";
return 0;
}
cout << "1\n";
for(int i = 1; i <= n; ++i)
if(id[i] < id[NOT(i)]) cout << i << " ";
return 0;
}
Bài viết được dựa trên các bài viết sau: