|BZOJ2199|2-SAT|[Usaco2011Jan]奶牛议会

BZOJ传送门
luogu免权限地址
2-SAT模板题，用2-SAT建图后，枚举每个议案能否通过

#include 
#include 
#include 
#include 
#define ms(i,j) memset(i,j, sizeof i); 
using namespace std; 
const int MAXN = 1000 + 5;
const char orz[10] = {'Y', 'N', '?'};
int n,m; 
int ans[MAXN];
struct twoSAT//这里标号从0开始 
{
    vector<int> G[MAXN*2];//邻接表 
    bool mark[MAXN*2];//每个点是否被标记 
    int n; 
    int init(int ni)//初始化 
    {
        n = ni;
        for (int i=0;i<2*n;i++) G[i].clear();
    }
    int addEdge(int x, int y, int xv, int yv)//加一个条件 
    {
        x = x*2+xv;
        y = y*2+yv;
        G[x^1].push_back(y);
        G[y^1].push_back(x);//2i是假，2i+1是真 
    }
    int dfs(int x)
    {
        if (mark[x^1]) return false;//对应点被标记，不符合要求 
        if (mark[x]) return true;//已经被标记直接返回
        mark[x] = true;//标记 
        for (int i=0;i//继续标记 
        {
            if (!dfs(G[x][i])) return false;
        } 
        return true;
    }
    int check(int x)//检查一个议案是否通过 
    {
        ms(mark, false); 
        return dfs(x);
    }
}ts;
int main()    
{     
    scanf("%d%d", &n,&m);
    ts.init(n);
    for (int i=0;iint bi,ci;
        char vbi,vci;
        scanf("%d %c %d %c", &bi,&vbi,&ci,&vci);
        int vvbi = false, vvci = false;
        if (vbi=='Y') vvbi = true;
        if (vci=='Y') vvci = true;
        ts.addEdge(bi-1,ci-1,vvbi,vvci);
    }
    for (int i=0;iint p = ts.check(i*2);
        int q = ts.check(i*2+1);
        if (!p&&!q) {printf("IMPOSSIBLE"); return 0;}
        if (p&&q) ans[i] = 2;
        else if (!p) ans[i] = 0;
        else ans[i] = 1;
    }
    for (int i=0;iputchar(orz[ans[i]]);
    return 0;    
}