模型的解决方法看论文《利用对称性解决2-SAT问题》

对于每两个人，二选一
HDU1814

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <vector>

using namespace std;

#define R 1//red 为ok

#define B 2//black 访问过但不ok

#define W 0//white 待染色

const int maxn = ;

vector<int>G[maxn];

int cnt,col[maxn],ans[maxn],n,m;

bool dfs(int u)

{

    if (col[u] == B) return false;

    if (col[u] == R) return true;

    col[u] = R;col[u^] = B;ans[cnt++]=u;

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

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

    return true;

}

bool _solve()

{

    int i, j;

    memset(col,,sizeof(col));

    for (i=; i<n; i++){

        if (col[i]) continue;

        cnt=;

        if (!_dfs(i)){

            for (j=;j<cnt;j++){

                col[ans[j]]=W;

                col[ans[j]^]=W;

            }

            if (!dfs(i^))  return false;

        }

    }

    return true;

}

int main()

{

    int i,a,b;

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

        n <<= ;//加倍

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

        while (m--){

            scanf("%d %d",&a, &b);

            a--;b--;

            G[a].push_back(b^);

            G[b].push_back(a^);

        }

        if (_solve()){

            for (i=; i<n; i++)

                if(col[i] == R)

                    printf("%d\n",i+);

        }

        else printf("NIE\n");

    }

    return ;

}

对于每个人留或者不留，二选一
HDU1824

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <vector>

using namespace std;

#define R 1

#define B 2

#define W 0

const int maxn = ;

vector<int>G[maxn];

int cnt,col[maxn],ans[maxn],n,m;

bool _dfs(int u)

{

    if (col[u] == B) return false;

    if (col[u] == R) return true;

    col[u] = R;col[u^] = B;ans[cnt++]=u;

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

        if (!_dfs(G[u][i])) return false;

    return true;

}

bool _solve()

{

    int i, j;

    memset(col,,sizeof(col));

    for (i=; i<n*; i++){

        if (col[i]) continue;

        cnt=;

        if (!_dfs(i)){

            for (j=;j<cnt;j++){

                col[ans[j]]=W;

                col[ans[j]^]=W;

            }

            if (!_dfs(i^))  return false;

        }

    }

    return true;

}

int main()

{

    int i,a,b,c;

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

        for(i=;i<n*;i++) G[i].clear();

        for(i=;i<=n;i++){

            scanf("%d%d%d",&a,&b,&c);

            a*=;b*=;c*=;

            G[a^].push_back(b);

            G[a^].push_back(c);

            G[b^].push_back(a);

            G[c^].push_back(a);

        }

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

            scanf("%d%d",&a,&b);

            a*=;b*=;

            G[a].push_back(b^);

            G[b].push_back(a^);

        }

        if (_solve()) printf("yes\n");

        else printf("no\n");

    }

    return ;

}