HDU 3062 简单的2-SAT问题

在2-SAT，最让我纠结的还是添加有向线段的函数了

void add_clause(int i,int a,int j,int b)
{
    int m=2*i+a;
    int n=2*j+b;
    G[m^1].push_back(n);
    G[n^1].push_back(m);
}

这里a，b因为只有真假两种情况，所以只取0或1，这里表示m V n是正确的，那么意思是取到m^1时，那么n必然得取到

同理取到n^1时，m必然取到，所以两条有向线段就添加成功了

例如这道题给所有夫妻排好序后，1号夫妻的丈夫，和3号夫妻的妻子有矛盾，那么来1号的妻子或3号中的丈夫是肯定成立的

那添加量就可以写成add_clause(1,0,3,1) (0表示妻子，1表示丈夫）

最后添加进去的就是G[3].push_back(7),G[6].push_back(2);

表示1号的丈夫来了，那只能让3号的丈夫来以及

要是3号的妻子来，那么只能让1号的妻子来才不会有矛盾

bool solve()
{
    for(int i=0;i<2*n;i+=2){
        if(!mark[i]&&!mark[i^1]){
            c=0;
            if(!dfs(i)){
                while(c>0) mark[S[--c]]=0;
                if(!dfs(i^1)) return false;
            }
        }

}
return true;
}

solve()中查找遍所有的夫妻对，表示当且仅当夫妻二人都不能来的时候返回false，否则返回true

总代码如下：

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

#define N 1005*2

bool mark[N];

vector<int> G[N];

int n,c,S[N];

bool dfs(int i)

{

    if(mark[i^]) return false;

    if(mark[i]) return true;

    mark[i]=true;

    S[c++]=i;

    for(int j=;j<G[i].size();j++)

        if(!dfs(G[i][j])) return false;

    return true;

}

void init()

{

    for(int i=;i<N;i++) G[i].clear();

    memset(mark,false,sizeof(mark));

    memset(S,,sizeof(S));

}

void add_clause(int i,int a,int j,int b)

{

    int m=*i+a;

    int n=*j+b;

    G[m^].push_back(n);

    G[n^].push_back(m);

}

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 false;

            }

        }

    }

    return true;

}

int main()

{

    int m,a1,a2,c1,c2;

    while(scanf("%d%d",&n,&m)!=EOF){

        init();

        for(int i=;i<m;i++){

            scanf("%d%d%d%d",&a1,&a2,&c1,&c2);

            add_clause(a1,c1^,a2,c2^);

        }

        if(solve()) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

巴特西

HDU 3062 简单的2-SAT问题

最新文章

热门文章