【小结】2-sat

时间：2015-07-17 22:47:22 阅读：302 评论：0 收藏：0 [点我收藏+]

$2-sat$ 小结

$2- sat$ 解决的是可满足性问题，并且每个合取范式中的文字个数不多于 $2$ 个。
形式为: $\left( a\lor \lnot b\right) \land \left( \lnot c\lor \lnot d\right)\land \left( \lnot a\lor d\right) \cdots$
将所有 $a\lor b$ 改成 $\left(\lnot a \Rightarrow b \right)\land \left(\lnot b \Rightarrow a\right)$
建边，每个变量 $a$ 对应两个点 $a$ 和 $a+n$
如果存在 $cmp[a]==cmp[a+n]$ 不成立，否则成立。且如果 $cmp[a]>cmp[a+n]$ ，令 $a=true$ ，否则令 $a=false$ 即为原式的一组解。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 1024;
vector<int> G[MAX];
vector<int> rG[MAX];
stack<int> S;
bool vis[MAX];
int cmp[MAX];
int V;

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int v)
{
    vis[v] = true;
    for (vector<int>::iterator it = G[v].begin(); it != G[v].end(); ++it)
    {
        if (!vis[*it])
        {
            dfs(*it);
        }
    }

    S.push(v);
}

void rdfs(int v, int k)
{
    vis[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!vis[rG[v][i]])
        {
            rdfs(rG[v][i], k);
        }
    }
}

int scc()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= V; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    memset(vis, false, sizeof(vis));
    int k = 0;

    while (!S.empty())
    {
        int p = S.top();
        S.pop();

        if (!vis[p])
        {
            rdfs(p, ++k);
        }
    }

    return k;
}

int main()
{

    /*
     * add_edge(u, v)
     * N nodes --> V = 2 * N
     * ...
     */
    /*
     * EXAMPLE: solve (a V !b) ^ (b V c) ^ (!c V !a)
     */
    int N = 3;
    V = N << 1;

    add_edge(3, 4);
    add_edge(1, 0);
    add_edge(4, 2);
    add_edge(5, 1);
    add_edge(2, 3);
    add_edge(0, 5);

    scc();

    bool ok = true;
    for (int i = 1; i <= N; ++i)
    {
        if (cmp[i] == cmp[i + N])
        {
            ok = false;
            break;
        }
    }

    if (ok)
    {
        puts("YES");
        for (int i = 1; i <= N; ++i)
        {
            printf("%s ", cmp[i] > cmp[i + N] ? "true" : "false");
        }
        puts("");
    }
    else
    {
        puts("NO");
    }

    return 0;
}

$POJ3683\ Priest\ John‘s\ Busiest\ Day$

问牧师能不能忙过来
对婚礼 $x$ ，记在开始举行仪式为 $x=true$ ，则可根据冲突关系，得出方程，求解即可。

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 2048;
vector<int> G[MAX];
vector<int> rG[MAX];
stack<int> stk;
bool vis[MAX];
int cmp[MAX];
int V;

inline void init()
{
    for (int i = 1; i <= V; ++i)
    {
        G[i].clear();
        rG[i].clear();
    }
}

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int u)
{
    vis[u] = true;
    for (int i = 0; i < G[u].size(); ++i)
    {
        if (!vis[G[u][i]])
        {
            dfs(G[u][i]);
        }
    }
    stk.push(u);
}

void rdfs(int u, int k)
{
    vis[u] = true;
    cmp[u] = k;
    for (int i = 0; i < rG[u].size(); ++i)
    {
        if (!vis[rG[u][i]])
        {
            rdfs(rG[u][i], k);
        }
    }
}

int scc()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= V; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    memset(vis, false, sizeof(vis));
    int k = 0;
    while (!stk.empty())
    {
        int p = stk.top();
        stk.pop();

        if (!vis[p])
        {
            rdfs(p, ++k);
        }
    }

    return k;
}

int S[MAX >> 1], T[MAX >> 1], D[MAX >> 1];

inline bool error(int l1, int r1, int l2, int r2)
{
    return l1 > l2 ? r2 > l1 : r1 > l2;
}

void gao(int n)
{
    V = n << 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            if (error(S[i], S[i] + D[i], S[j], S[j] + D[j]))
            {
                add_edge(i, j + n);
                add_edge(j, i + n);
            }
            if (error(S[i], S[i] + D[i], T[j] - D[j], T[j]))
            {
                add_edge(i, j);
                add_edge(j + n, i + n);
            }
            if (error(T[i] - D[i], T[i], S[j], S[j] + D[j]))
            {
                add_edge(i + n, j + n);
                add_edge(j, i);
            }
            if (error(T[i] - D[i], T[i], T[j] - D[j], T[j]))
            {
                add_edge(i + n, j);
                add_edge(j + n, i);
            }
        }
    }

    scc();
    //printf("%d\n", scc()); //scc();

    for (int i = 1; i <= n; ++i)
    {
        if (cmp[i] == cmp[i + n])
        {
            puts("NO");
            return;
        }
    }

    puts("YES");
    for (int i = 1; i <= n; ++i)
    {
        if (cmp[i] > cmp[i + n])
        {
            printf("%02d:%02d %02d:%02d\n", S[i] / 60, S[i] % 60, (S[i] + D[i]) / 60, (S[i] + D[i]) % 60);
        }
        else
        {
            printf("%02d:%02d %02d:%02d\n", (T[i] - D[i]) / 60, (T[i] - D[i]) % 60, T[i] / 60, T[i] % 60);
        }
    }
}

int main()
{
    int N;
    while (~scanf(" %d", &N))
    {
        int h, m;
        for (int i = 1; i <= N; ++i)
        {
            scanf(" %d:%d", &h, &m);
            S[i] = h * 60 + m;
            scanf(" %d:%d", &h, &m);
            T[i] = h * 60 + m;
            scanf(" %d", D + i);

            //printf("%d:[%d, %d]:%d\n", i, S[i], T[i], D[i]);
        }
        gao(N);
    }
    return 0;
}

$HDU3062$

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1024;
vector<int> G[MAX << 1];
vector<int> rG[MAX << 1];
bool vis[MAX << 1];
int cmp[MAX << 1];
stack<int> stk;
int V;

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int u)
{
    vis[u] = true;
    for (int i = 0; i < G[u].size(); ++i)
    {
        if (!vis[G[u][i]])
        {
            dfs(G[u][i]);
        }
    }
    stk.push(u);
}

void dfs2(int u, int k)
{
    vis[u] = true;
    cmp[u] = k;
    for (int i = 0; i < rG[u].size(); ++i)
    {
        if (!vis[rG[u][i]])
        {
            dfs2(rG[u][i], k);
        }
    }
}

int scc()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= V; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    memset(vis, false, sizeof(vis));
    int k = 0;
    while (!stk.empty())
    {
        int p = stk.top();
        stk.pop();

        if (!vis[p])
        {
            dfs2(p, ++k);
        }

    }
    return k;
}

bool gao(int n)
{
    scc();

    for (int i = 1; i <= n; ++i)
    {
        if (cmp[i] == cmp[i + n])
        {
            return false;
        }
    }
    return true;
}

inline void read(int& x)
{
    char ch;
    while ((ch = getchar()) < ‘0‘ || ch > ‘9‘);

    x = ch - ‘0‘;
    while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)
    {
        x = (x << 3) + (x << 1) + ch - ‘0‘;
    }
}

int main()
{
    int n, m;
    while (~scanf(" %d %d", &n, &m))
    {
        V = n << 1;
        for (int i = 1; i <= V; ++i)
        {
            G[i].clear();
            rG[i].clear();
        }

        int a1, a2, c1, c2;
        while (m--)
        {
            //scanf(" %d %d %d %d", &a1, &a2, &c1, &c2);
            read(a1);
            read(a2);
            read(c1);
            read(c2);
            if (c1 > 0)
            {
                a1 += n;
            }
            if (c2 > 0)
            {
                a2 += n;
            }

            /* 
             * !a1 V !a2
             * <->  ((a1 -> !a2) V (a2 -> !a1))
             */
            add_edge(a1, a2 > n ? a2 - n : a2 + n);
            add_edge(a2, a1 > n ? a1 - n : a1 + n);
        }
        puts(gao(n) ? "YES" : "NO");
    }
    return 0;
}

$HDU\ 1824$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 1024 * 3 * 2;
vector<int> G[MAX];
vector<int> rG[MAX];
stack<int> S;
bool vis[MAX];
int cmp[MAX];
int V;

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int v)
{
    vis[v] = true;
    for (vector<int>::iterator it = G[v].begin(); it != G[v].end(); ++it)
    {
        if (!vis[*it])
        {
            dfs(*it);
        }
    }

    S.push(v);
}

void rdfs(int v, int k)
{
    vis[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!vis[rG[v][i]])
        {
            rdfs(rG[v][i], k);
        }
    }
}

int scc()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= V; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    memset(vis, false, sizeof(vis));
    int k = 0;

    while (!S.empty())
    {
        int p = S.top();
        S.pop();

        if (!vis[p])
        {
            rdfs(p, ++k);
        }
    }

    return k;
}

bool gao(int N)
{
    scc();

    for (int i = 1; i <= N; ++i)
    {
        if (cmp[i] == cmp[i + N])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int T, M;
    while (~scanf(" %d %d", &T, &M))
    {
        V = T * 3 * 2;
        int N = T * 3;
        for (int i = 0; i <= V; ++i)
        {
            G[i].clear();
            rG[i].clear();
        }

        int c, a, b;
        for (int i = 1; i <= T; ++i)
        {
            scanf(" %d %d %d", &c, &a, &b);
            ++c, ++a, ++b;
            add_edge(c + N, a);
            add_edge(c + N, b);

            add_edge(a + N, c);
            add_edge(b + N, c);

            add_edge(c, a + N);
            add_edge(c, b + N);
            add_edge(a, c + N);
            add_edge(b, c + N);
        }

        for (int i = 1; i <= M; ++i)
        {
            scanf(" %d %d", &a, &b);
            ++a, ++b;
            add_edge(a, b + N);
            add_edge(b, a + N);
        }

        puts(gao(N) ? "yes" : "no");
    }

    return 0;
}

$POJ\ 3207$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 1024;
vector<int> G[MAX];
vector<int> rG[MAX];
stack<int> S;
bool vis[MAX];
int cmp[MAX];
pair<int, int> line[MAX >> 1];
int V;

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int v)
{
    vis[v] = true;
    for (vector<int>::iterator it = G[v].begin(); it != G[v].end(); ++it)
    {
        if (!vis[*it])
        {
            dfs(*it);
        }
    }

    S.push(v);
}

void rdfs(int v, int k)
{
    vis[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!vis[rG[v][i]])
        {
            rdfs(rG[v][i], k);
        }
    }
}

int scc()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= V; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    memset(vis, false, sizeof(vis));
    int k = 0;

    while (!S.empty())
    {
        int p = S.top();
        S.pop();

        if (!vis[p])
        {
            rdfs(p, ++k);
        }
    }

    return k;
}

bool gao(int n)
{

    scc();

    for (int i = 1; i <= n; ++i)
    {
        if (cmp[i] == cmp[i + n])
        {
            return false;
        }
    }

    return true;
}

bool error(int x1, int y1, int x2, int y2)
{
    int xx = min(x1, y1);
    int yy = min(x1, y1);
    return (x2 > xx && x2 > yy) || (y2 > xx && y2 > yy)
        || (x2 > xx && x2 < yy) || (y2 > xx && y2 < yy)
        || (x2 < xx && x2 < yy) || (y2 < xx && y2 < yy);
}

int main()
{
    int n, m;
    while (~scanf(" %d %d", &n, &m))
    {
        V = m << 1;
        for (int i = 1; i <= V; ++i)
        {
            G[i].clear();
            rG[i].clear();
        }
        int a, b;
        for (int i = 1; i <= m; ++i)
        {
            scanf(" %d %d", &line[i].first, &line[i].second);
            ++line[i].first, ++line[i].second;
        }

        for (int i = 1; i <= m; ++i)
        {
            for (int j = i + 1; j <= m; ++j)
            {
                if (error(line[i].first, line[i].second, line[j].first, line[j].second))
                {
                    printf("error at (%d, %d)\n", i, j);
                    //add_edge
                    add_edge(i, j + m);
                    add_edge(j, i + m);
                }
            }
        }

        puts(gao(m) ? "panda is telling the truth..." : "the evil panda is lying again");
        for (int i = 1; i <= m; ++i)
        {
            if (cmp[i] > cmp[i + m])
            {
                printf("true ");
            }
            else
            {
                printf("false ");
            }
        }
        puts("");
    }
    return 0;
}

【小结】2-sat

原文：http://blog.csdn.net/bit_line/article/details/46932299

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

【小结】2-sat

2?sat2-sat 小结

POJ3683 Priest John′s Busiest DayPOJ3683\ Priest\ John‘s\ Busiest\ Day

HDU3062HDU3062

HDU 1824HDU\ 1824

POJ 3207POJ\ 3207

$2-sat$ 小结

$POJ3683\ Priest\ John‘s\ Busiest\ Day$

$HDU3062$

$HDU\ 1824$

$POJ\ 3207$