首页 > 代码库 > HDU 3062 简单的2-SAT问题

HDU 3062 简单的2-SAT问题

2024-07-16 01:41:57   214人阅读

在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*2bool mark[N];vector<int> G[N];int n,c,S[N];bool dfs(int i){    if(mark[i^1]) return false;    if(mark[i]) return true;    mark[i]=true;    S[c++]=i;    for(int j=0;j<G[i].size();j++)        if(!dfs(G[i][j])) return false;    return true;}void init(){    for(int i=0;i<N;i++) G[i].clear();    memset(mark,false,sizeof(mark));    memset(S,0,sizeof(S));}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);}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;}int main(){    int m,a1,a2,c1,c2;    while(scanf("%d%d",&n,&m)!=EOF){        init();        for(int i=0;i<m;i++){            scanf("%d%d%d%d",&a1,&a2,&c1,&c2);            add_clause(a1,c1^1,a2,c2^1);        }        if(solve()) printf("YES\n");        else printf("NO\n");    }    return 0;}
View Code

 


联系
我们