图论$\cdot$2-SAT问题

2-SAT问题是这样的：有$n$个布尔变量$x_i$，另有$m$个需要满足的条件，每个条件的形式都是“$x_i$为真/假或者$x_j$为真/假”。比如："$x_1$为真或者$x_3$为假“。注意这里的”或“是指两个条件至少有一个是正确的，比如$x_1$和$x_3$一共有$3$中组合满足"$x_1$为真或者$x_3$为假“。2-SAT问题的目标是给每个变量赋值，使得所有条件得到满足。求解2-SAT问题一般比较常见方法是构造一张有向图$G$，其中每个变量$x_i$拆成两个结点$2i$和$2i+1$，分别表示$x_i$为假和$x_i$为真。最后要为每个变量选择其中一个结点标记。比如，若标记了节点$2i$，表示$x_i$为假；如果标记了$2i+1$，表示$x_i$为真。对于“$x_i$为假或者$x_j$为假”这样的条件，我们连一条有向边$2i+1 \rightarrow 2j$，表示如果标记节点$2i+1$那么也必须标记结点$j$，同理还需要连一条有向边$2j+1 \rightarrow 2i$。对于其他情况，也可以类似连边。换句话说，每个条件对应两条“对称”的边。接下来逐一考虑每个没有赋值的变量，设为$x_i$。我们首先假定它为假，然后标记借点$2_i$，并且沿着有向边标记所有能标记的结点。如果标记过程中发现某个变量对应的两个结点都被标记，则“$x_i$为假”这个假定不成立，需要改成“$x_i$为真”，然后重新标记。注意，该算法无回溯过程。如果当前考虑的变量不管赋值为真还是假都会引起矛盾，可以证明整个2-SAT问题无解（即使调整以前赋值的变量也没用）。这是很显然的，每个变量只会影响到关系到该变量的表达式的取值，因此对于未赋值的变量一定与之前的赋值无关，可以分开考虑，整个问题有解需要满足每个块都有解。下面给出求解2-SAT问题的代码：

 struct _2_sat{

     int n;

     vector<int> G[maxn << ];

     bool mark[maxn << ];

     int S[maxn << ], c;

     bool dfs(int x){

         if(mark[x ^ ]) return ;

         if(mark[x]) return ;

         mark[x] = ;

         S[c++] = x;

         FOR(i, , G[x].size() - ) if(!dfs(G[x][i])) return ;

         return ;

     }

     void init(int n){

         this->n = n;

         FOR(i, ,  * n - ) G[i].clear();

         clr(mark, );

     }

     //x = xval or y = yval

     void add_caluse(int x, int xval, int y, int yval){

         x = x *  + xval, y = y *  + yval;

         G[x ^ ].pb(y), G[y ^ ].pb(x);

     }

     bool solve(){

         for(int i = ; i <  * n; i += ) if(!mark[i] && !mark[i + ]){

             c = ;

             if(!dfs(i)){

                 while(c > ) mark[S[--c]] = ;

                 if(!dfs(i + )) return ;

             }

         }

         return ;

     }

 };

相关习题：

LA 3713 Astronauts

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <map>

 #include <set>

 #include <stack>

 #include <ctime>

 #include <cmath>

 #include <iostream>

 #include <assert.h>

 #pragma comment(linker, "/STACK:102400000,102400000")

 #define max(a, b) ((a) > (b) ? (a) : (b))

 #define min(a, b) ((a) < (b) ? (a) : (b))

 #define mp std :: make_pair

 #define st first

 #define nd second

 #define keyn (root->ch[1]->ch[0])

 #define lson (u << 1)

 #define rson (u << 1 | 1)

 #define pii std :: pair<int, int>

 #define pll pair<ll, ll>

 #define pb push_back

 #define type(x) __typeof(x.begin())

 #define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)

 #define FOR(i, s, t) for(int i = (s); i <= (t); i++)

 #define ROF(i, t, s) for(int i = (t); i >= (s); i--)

 #define dbg(x) std::cout << x << std::endl

 #define dbg2(x, y) std::cout << x << " " << y << std::endl

 #define clr(x, i) memset(x, (i), sizeof(x))

 #define maximize(x, y) x = max((x), (y))

 #define minimize(x, y) x = min((x), (y))

 using namespace std;

 typedef long long ll;

 const int int_inf = 0x3f3f3f3f;

 const ll ll_inf = 0x3f3f3f3f3f3f3f3f;

 const int INT_INF = (int)((1ll << ) - );

 const double double_inf = 1e30;

 const double eps = 1e-;

 typedef unsigned long long ul;

 typedef unsigned int ui;

 inline int readint(){

     int x;

     scanf("%d", &x);

     return x;

 }

 inline int readstr(char *s){

     scanf("%s", s);

     return strlen(s);

 }

 class cmpt{

 public:

     bool operator () (const int &x, const int &y) const{

         return x > y;

     }

 };

 int Rand(int x, int o){

     //if o set, return [1, x], else return [0, x - 1]

     if(!x) return ;

     int tem = (int)((double)rand() / RAND_MAX * x) % x;

     return o ? tem +  : tem;

 }

 ll ll_rand(ll x, int o){

     if(!x) return ;

     ll tem = (ll)((double)rand() / RAND_MAX * x) % x;

     return o ? tem +  : tem;

 }

 void data_gen(){

     srand(time());

     freopen("in.txt", "w", stdout);

     int kases = ;

     printf("%d\n", kases);

     while(kases--){

         ll sz = ;

         printf("%d\n", sz);

         FOR(i, , sz){

             int o = Rand(, );

             int x = Rand(1e9, );

             int y1 = Rand(1e9, ), y2 = Rand(1e9, );

             if(o == ) printf("%d %d %d %d\n", x, y1, x, y1);

             else printf("%d %d %d %d\n", y1, x, y2, x);

         }

     }

 }

 const int maxn = 1e5 + ;

 int n, m;

 ll sum;

 int id[maxn];

 int age[maxn];

 int head[maxn << ];

 struct E{

     int to, nex;

 }e[maxn << ];

 bool vis[maxn << ];

 int N;

 void addE(int x, int y){

     e[N].nex = head[x];

     e[N].to = y;

     head[x] = N++;

 }

 int stk[maxn], k;

 bool dfs(int u){

     if(vis[u]) return ;

     vis[u] = ;

     stk[k++] = u;

     if(vis[u] && vis[u ^ ]) return ;

     for(int i = head[u]; ~i; i = e[i].nex){

         int v = e[i].to;

         if(!dfs(v)) return ;

     }

     return ;

 }

 bool solve(int u){

     k = ;

     if(dfs( * u)) return ;

     while(k) vis[stk[--k]] = ;

     if(dfs( * u + )) return ;

     return ;

 }

 int main(){

     //data_gen(); return 0;

     //C(); return 0;

     int debug = ;

     if(debug) freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

     while(~scanf("%d%d", &n, &m) && n){

         sum = ;

         FOR(i, , n - ) age[i] = readint(), sum += age[i];

         FOR(i, , n - ) id[i] = (ll)age[i] * n >= sum ?  : ;

         clr(head, -), N = ;

         FOR(i, , m - ){

             int x = readint() - , y = readint() - ;

             //cc[i][0] = x, cc[i][1] = y;

             addE( * x,  * y + );

             if(id[x] == id[y]) addE( * x + ,  * y);

             addE( * y,  * x + );

             if(id[x] == id[y]) addE( * y + ,  * x);

         }

         int ok = ;

         clr(vis, );

         FOR(i, , n - ) if(!vis[ * i] && !vis[ * i + ] && !solve(i)){

             ok = ;

             break;

         }

         if(!ok) puts("No solution.");

         else FOR(i, , n - ) putchar(!vis[ * i + ] ? 'C' : 'A' + id[i]), putchar('\n');

         //int res = verdict();

         //printf("verdict :: %s", res ? "ok\n" : "err\n");

     }

     return ;

 }

code:

巴特西

图论$\cdot$2-SAT问题

最新文章

热门文章