首页 / 更多教程 / 讨论2-sat建设和解决问题
讨论2-sat建设和解决问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了讨论2-sat建设和解决问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12112字，纯文字阅读大概需要18分钟。
内容图文
2-sat问题是一种常见的问题。给定若干个01变量，变量之间满足一些二元约束，求是否有解存在。若存在，给出可行解或依照字典序给出最优解。
以下给出与其相应的图论模型：给每一个变量i设立2个点，我的习惯是记为T(i),F(i),分别表示其值取1,0.
以下考虑的便是怎样进行限制了。
一般的限制形式均例如以下所看到的：
变量i取x时，变量j仅仅能取y,那么表示i取x的点向表示j取y的点连一条有向边。表示推出关系。
类似的，若表示变量i取x时，变量j不能取y，那么表示i取x的点向表示j取~y的点连一条有向边。由于每一个变量必然有值，且仅仅有一个值。
以上这些限制每次都须要连两条边，即原命题和其逆否命题。
有一些另外的限制比較特殊：即变量i仅仅能取x,那么表示i取~x的点向表示i取x的点连一条有向边.若表示变量i不能取x,那么表示i取x的点向表示i取~x的点连一条有向边.这些限制仅仅连一条边。
接下来，利用Tarjan算法求解强联通分量，若表示某个变量为0的点和表示这个变量为1的点在同一个强联通分量中，表示存在矛盾，2-sat问题无解。
以下看一下怎样求出一组可行解。
我们构造求出的DAG的反图，按照拓扑序依次进行处理。对于当前点，若没有被染色，则染色为1，并将这个连通分量中全部点的还有一个解所相应的点所在的分量及其子孙均染色为2.（注意，这是在反图中。）染色就递归去染就好了，当遇到一个已经被染色为2的点就不向下染色了。
那么终于每一个变量的解就是被染色为1的分量所包括的该变量所相应的解。
以下来看几道题：
POJ3207
Sol：以这条边在圈内作为0，在圈外作为1，限制就是假设两条边区间相交，那么值不能同样。那么T(i)->F(j),T(j)->F(i).仅仅需推断这个2-sat问题是否有解就可以。
Code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 510
int l[N], r[N];
int head[N << 1], next[N * N << 2], end[N * N << 2];
void addedge(int a, int b) {
static int q = 1;
end[q] = b;
next[q] = head[a];
head[a] = q++;
}
#define T(i) (i << 1)
#define F(i) ((i << 1) | 1)
int dfn[N << 1], low[N << 1], tclock, stack[N << 1], top, belong[N << 1], num;
bool instack[N << 1];
void dfs(int x) {
dfn[x] = low[x] = ++tclock;
stack[++top] = x;
instack[x] = 1;
for(int j = head[x]; j; j = next[j]) {
if (!dfn[end[j]])
dfs(end[j]), low[x] = min(low[x], low[end[j]]);
else if (instack[end[j]])
low[x] = min(low[x], dfn[end[j]]);
}
if (low[x] == dfn[x]) {
++num;
while(1) {
int i = stack[top--];
belong[i] = num;
instack[i] = 0;
if (i == x)
break;
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
register int i, j;
int a, b;
for(i = 1; i <= m; ++i) {
scanf("%d%d", &a, &b);
l[i] = ++a;
r[i] = ++b;
if (l[i] > r[i])
swap(l[i], r[i]);
}
for(i = 1; i <= m; ++i) {
for(j = i + 1; j <= m; ++j) {
if (l[j] > l[i] && l[j] < r[i] && r[j] > r[i]) {
addedge(T(i), F(j));
addedge(F(i), T(j));
addedge(T(j), F(i));
addedge(F(j), T(i));
}
}
}
for(i = T(1); i <= F(m); ++i)
if (!dfn[i])
dfs(i);
bool find = 0;
for(i = 1; i <= m; ++i)
if (belong[T(i)] == belong[F(i)]) {
find = 1;
break;
}
if (find)
puts("the evil panda is lying again");
else
puts("panda is telling the truth...");
return 0;
}
BZOJ1997
Sol:基本和上道题类似。也仅仅须要推断是否有解。
Code:
#include <cctype>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
inline int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
inline int getint() {
int c;
while(!isdigit(c = getc()));
int tmp = c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
#define N 210
#define M 10010
int hash[N];
struct Edge {
int f, t;
Edge(int _f = 0, int _t = 0):f(_f),t(_t){}
}E[M], sav[M];
int top;
struct Graph {
int head[1210], next[819200], end[819200], ind;
int dfn[1210], low[1210], tclock, stack[1210], top, belong[1210], cnt;
bool instack[1210];
void reset() {
ind = tclock = top = cnt = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
}
void addedge(int a, int b) {
int q = ind++;
end[q] = b;
next[q] = head[a];
head[a] = q;
}
void dfs(int x) {
dfn[x] = low[x] = ++tclock;
instack[x] = 1;
stack[++top] = x;
for(int j = head[x]; j != -1; j = next[j]) {
if (!dfn[end[j]]) {
dfs(end[j]);
low[x] = min(low[x], low[end[j]]);
}
else if (instack[end[j]])
low[x] = min(low[x], dfn[end[j]]);
}
if (low[x] == dfn[x]) {
++cnt;
while(1) {
int i = stack[top--];
belong[i] = cnt;
instack[i] = 0;
if (x == i)
break;
}
}
}
}G;
#define T(i) (i * 2 - 2)
#define F(i) (i * 2 - 1)
inline bool is_intersect(int i, int j) {
return sav[j].f > sav[i].f && sav[j].f < sav[i].t && sav[j].t > sav[i].t;
}
int main() {
int T = getint();
register int i, j;
int n, m;
while(T--) {
n = getint(), m = getint();
for(i = 1; i <= m; ++i)
E[i].f = getint(), E[i].t = getint();
int x;
for(i = 1; i <= n; ++i) {
x = getint();
hash[x] = i;
}
if (m > 3 * n + 6) {
puts("NO");
continue;
}
top = 0;
int f, t;
for(i = 1; i <= m; ++i) {
f = hash[E[i].f], t = hash[E[i].t];
if (f > t)
swap(f, t);
if (!((f + 1 == t) || (f == 1 && t == n))) {
sav[++top] = Edge(f, t);
}
}
G.reset();
for(i = 1; i <= top; ++i) {
for(j = i + 1; j <= top; ++j) {
if (is_intersect(i, j) || is_intersect(j, i)) {
G.addedge(T(i), F(j));
G.addedge(F(i), T(j));
G.addedge(T(j), F(i));
G.addedge(F(j), T(i));
}
}
}
for(i = T(1); i <= F(top); ++i)
if (!G.dfn[i])
G.dfs(i);
bool find = 0;
for(i = 1; i <= top; ++i)
if (G.belong[T(i)] == G.belong[F(i)]) {
find = 1;
break;
}
if (find)
puts("NO");
else
puts("YES");
}
return 0;
}POJ3678
Sol:一堆乱七八糟的位运算。。。涉及到某变量强制取值的建模技巧。仅仅需推断是否有解。
Code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1010
#define M 1000010
int head[N << 1], end[M << 2], next[M << 2];
void addedge(int a, int b) {
static int q = 1;
end[q] = b;
next[q] = head[a];
head[a] = q++;
}
#define T(i) (i << 1)
#define F(i) ((i << 1) | 1)
int dfn[N << 1], low[N << 1], tclock, stack[N << 1], top, belong[N << 1], num;
bool instack[N << 1];
void dfs(int x) {
dfn[x] = low[x] = ++tclock;
stack[++top] = x;
instack[x] = 1;
for(int j = head[x]; j; j = next[j]) {
if (!dfn[end[j]]) {
dfs(end[j]);
low[x] = min(low[x], low[end[j]]);
}
else if (instack[end[j]])
low[x] = min(low[x], dfn[end[j]]);
}
if (dfn[x] == low[x]) {
++num;
while(1) {
int i = stack[top--];
belong[i] = num;
instack[i] = 0;
if (i == x)
break;
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
register int i;
char s[10];
int a, b, x;
for(i = 1; i <= m; ++i) {
scanf("%d%d%d%s", &a, &b, &x, s);
++a, ++b;
if (s[0] == 'A') {
if (x) {
addedge(F(a), T(a));
addedge(F(b), T(b));
}
else {
addedge(T(a), F(b));
addedge(T(b), F(a));
}
}
if (s[0] == 'O') {
if (x) {
addedge(F(a), T(b));
addedge(F(b), T(a));
}
else {
addedge(T(a), F(a));
addedge(T(b), F(b));
}
}
if (s[0] == 'X') {
if (x) {
addedge(T(a), F(b));
addedge(F(a), T(b));
addedge(T(b), F(a));
addedge(F(b), T(a));
}
else {
addedge(T(a), T(b));
addedge(F(a), F(b));
addedge(T(b), T(a));
addedge(F(b), F(a));
}
}
}
for(i = T(1); i <= F(n); ++i)
if (!dfn[i])
dfs(i);
bool find = 0;
for(i = 1; i <= n; ++i) {
if (belong[T(i)] == belong[F(i)]) {
find = 1;
break;
}
}
if (find)
puts("NO");
else
puts("YES");
return 0;
}POJ3683
Sol:每一个婚礼分为是开头还是结尾作为01取值，建模非常easy，若区间相交则矛盾就可以。
比較锻炼代码能力的一道题。。。
Code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define N 1010
int l[N], r[N], len[N];
int get(char *s) {
return 600*(s[0]-'0')+60*(s[1]-'0')+10*(s[3]-'0')+(s[4]-'0');
}
int head[N << 1], next[N * N << 3], end[N * N << 3];
void addedge(int a, int b) {
static int q = 1;
end[q] = b;
next[q] = head[a];
head[a] = q++;
}
#define T(i) (i << 1)
#define F(i) ((i << 1) | 1)
int dfn[N << 1], low[N << 1], tclock, stack[N << 1], top, belong[N << 1], num;
vector<int> sav[N << 1];
bool instack[N << 1];
void dfs(int x) {
dfn[x] = low[x] = ++tclock;
stack[++top] = x;
instack[x] = 1;
for(int j = head[x]; j; j = next[j]) {
if (!dfn[end[j]]) {
dfs(end[j]);
low[x] = min(low[x], low[end[j]]);
}
else if (instack[end[j]])
low[x] = min(low[x], dfn[end[j]]);
}
if (dfn[x] == low[x]) {
++num;
while(1) {
int i = stack[top--];
instack[i] = 0;
belong[i] = num;
sav[num].push_back(i);
if (x == i)
break;
}
}
}
queue<int> q;
struct Graph {
int head[N << 1], next[N * N << 3], end[N * N << 3], in[N << 1], ind, col[N << 1];
void reset() {
ind = 0;
memset(head, -1, sizeof(head));
}
void addedge(int a, int b) {
int q = ind++;
end[q] = b;
next[q] = head[a];
head[a] = q;
++in[b];
}
void Paint(int x) {
col[x] = 2;
for(int j = head[x]; j != -1; j = next[j])
if (col[end[j]] != 2)
Paint(end[j]);
}
void TopoSort() {
int i, j;
for(i = 1; i <= num; ++i)
if (!in[i])
q.push(i);
while(!q.empty()) {
i = q.front();
q.pop();
if (!col[i]) {
col[i] = 1;
int size = sav[i].size();
for(j = 0; j < size; ++j)
Paint(belong[sav[i][j] ^ 1]);
}
for(j = head[i]; j != -1; j = next[j])
if (!--in[end[j]])
q.push(end[j]);
}
}
}G;
bool isnot_insect(int l1, int r1, int l2, int r2) {
return r1 <= l2 || r2 <= l1;
}
void print(int x) {
int t = x % 60;
printf("%02d:%02d", (x - t) / 60, t);
}
int main() {
int n;
scanf("%d", &n);
char s1[10], s2[10];
int i, j;
for(i = 1; i <= n; ++i) {
scanf("%s%s%d", s1, s2, &len[i]);
l[i] = get(s1);
r[i] = get(s2);
}
for(i = 1; i <= n; ++i) {
for(j = i + 1; j <= n; ++j) {
if (!isnot_insect(l[i], l[i] + len[i], l[j], l[j] + len[j])) {
addedge(T(i), F(j));
addedge(T(j), F(i));
}
if (!isnot_insect(l[i], l[i] + len[i], r[j] - len[j], r[j])) {
addedge(T(i), T(j));
addedge(F(j), F(i));
}
if (!isnot_insect(r[i] - len[i], r[i], l[j], l[j] + len[j])) {
addedge(F(i), F(j));
addedge(T(j), T(i));
}
if (!isnot_insect(r[i] - len[i], r[i], r[j] - len[j], r[j])) {
addedge(F(i), T(j));
addedge(F(j), T(i));
}
}
}
for(i = T(1); i <= F(n); ++i)
if (!dfn[i])
dfs(i);
bool find = 0;
for(i = 1; i <= n; ++i)
if (belong[T(i)] == belong[F(i)]) {
find = 1;
break;
}
if (find) {
puts("NO");
return 0;
}
G.reset();
for(i = T(1); i <= F(n); ++i)
for(j = head[i]; j; j = next[j])
if (belong[i] != belong[end[j]])
G.addedge(belong[end[j]], belong[i]);
G.TopoSort();
puts("YES");
for(i = 1; i <= n; ++i) {
if (G.col[belong[T(i)]] == 1)
print(l[i]), putchar(' '), print(l[i] + len[i]);
else
print(r[i] - len[i]), putchar(' '), print(r[i]);
puts("");
}
return 0;
}BZOJ1823
Sol:十分的裸题。。。
Code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 110
#define M 1010
struct Graph {
int head[N << 1], next[M << 1], end[M << 1], ind;
int dfn[N << 1], low[N << 1], tclock, stack[N << 1], top, belong[N << 1], num;
bool instack[N << 1];
void reset() {
ind = tclock = top = num = 0;
memset(dfn, 0, sizeof(dfn));
memset(head, -1, sizeof(head));
}
void addedge(int a, int b) {
int q = ind++;
end[q] = b;
next[q] = head[a];
head[a] = q;
}
void dfs(int x) {
dfn[x] = low[x] = ++tclock;
instack[x] = 1;
stack[++top] = x;
for(int j = head[x]; j != -1; j = next[j]) {
if (!dfn[end[j]]) {
dfs(end[j]);
low[x] = min(low[x], low[end[j]]);
}
else if (instack[end[j]])
low[x] = min(low[x], dfn[end[j]]);
}
if (dfn[x] == low[x]) {
++num;
while(1) {
int i = stack[top--];
belong[i] = num;
instack[i] = 0;
if (x == i)
break;
}
}
}
}G;
#define T(i) (i << 1)
#define F(i) ((i << 1) | 1)
int getint(char *s) {
int len = strlen(s);
int res = 0;
for(int i = 1; i < len; ++i)
res = (res << 3) + (res << 1) + s[i] - '0';
return res;
}
int main() {
int Case;
scanf("%d", &Case);
int n, m;
char s1[60], s2[60];
register int i, j;
bool b1, b2;
int n1, n2;
while(Case--) {
G.reset();
scanf("%d%d", &n, &m);
for(i = 1; i <= m; ++i) {
scanf("%s%s", s1, s2);
b1 = (s1[0] == 'm');
b2 = (s2[0] == 'm');
n1 = getint(s1);
n2 = getint(s2);
if (b1 && b2)
G.addedge(F(n1), T(n2)), G.addedge(F(n2), T(n1));
if (b1 && !b2)
G.addedge(F(n1), F(n2)), G.addedge(T(n2), T(n1));
if (!b1 && b2)
G.addedge(T(n1), T(n2)), G.addedge(F(n2), F(n1));
if (!b1 && !b2)
G.addedge(T(n1), F(n2)), G.addedge(T(n2), F(n1));
}
for(i = T(1); i <= F(n); ++i)
if (!G.dfn[i])
G.dfs(i);
bool find = 0;
for(i = 1; i <= n; ++i)
if (G.belong[T(i)] == G.belong[F(i)]) {
find = 1;
break;
}
if (find)
puts("BAD");
else
puts("GOOD");
}
return 0;
}就到这里结束怎样？
原文：http://www.cnblogs.com/gcczhongduan/p/4558105.html
内容总结
以上是互联网集市为您收集整理的讨论2-sat建设和解决问题全部内容，希望文章能够帮你解决讨论2-sat建设和解决问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】