问一下建图思路

我是一种材料拆成四个点（分别用n * 4,n * 4 + 1, n * 4 + 2, n * 4 + 3代表汉式做，汉式不做，满式做，满式不做），对于同一种材料满足汉式满式二选一，（即 汉式 xor 满式 = 1，连边如下：）

for(int i = 1;i <= num;i++){
            int x = i * 2, y = i * 2 + 1;
            add(x << 1, y << 1 | 1, 1);
            add(y << 1, x << 1 | 1, 1);
            add(x << 1 | 1, y << 1, 1);
            add(y << 1 | 1, x << 1, 1);
            }

对于每个评委的要求满足两个至少选其一（即 要求1 or 要求2 = 1，连边如下）

for(int i = 1;i <= nr;i++){
            c = getchar();
            x = RD() * 2;
            if(c == 'm')x++;
            c = getchar();
            y = RD() * 2;
            if(c == 'm')y++;
            add(x << 1, y << 1 | 1, 1);
            add(y << 1, x << 1 | 1, 1);
            }

检查时若是一种材料同时做了满式和汉式（即col[做汗] = col[做满] ），或是一样菜同时要求做和不做（即 col[做] = col[不做] ）则不合法，代码如下：

bool check(){
    for(int i = 1;i <= num;i++){
        int x = i << 1, y = i << 1 | 1;
        if(col[x << 1 | 1] == col[y << 1 | 1])return 0;
        }
    for(int i = 2;i <= (num << 1 | 1);i++){
        if(col[i << 1] == col[i << 1 | 1])return 0;
        }
    return 1;
    }

只有10分，查不出错了

附上全部代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 2000019,INF = 1e9 + 19;
int head[maxn],nume = 1;
struct Node{
    int v,dis,nxt;
    }E[maxn << 2];
void add(int u,int v,int dis){
    E[++nume].nxt = head[u];
    E[nume].v = v;
    E[nume].dis = dis;
    head[u] = nume;
    }
int num, nr, T;
int DFN[maxn], LOW[maxn], INDEX;
int S[maxn], top;
bool ins[maxn];
int col[maxn], numc;
void Tarjan(int u){
    DFN[u] = LOW[u] = ++INDEX;
    S[++top] = u;ins[u] = 1;
    for(int i = head[u];i;i = E[i].nxt){
        int v = E[i].v;
        if(!DFN[v])Tarjan(v), LOW[u] = min(LOW[u], LOW[v]);
        else if(ins[v])LOW[u] = min(LOW[u], DFN[v]);
        }
    if(DFN[u] == LOW[u]){
        numc++;
        while(S[top + 1] != u){
            col[S[top]] = numc;
            ins[S[top--]] = 0;
            }
        }
    }
void init(){
    memset(head, 0, sizeof(head));
    nume = 1;
    memset(DFN, 0, sizeof(DFN));
    memset(LOW, 0, sizeof(LOW));
    INDEX = 0;
    memset(col, 0, sizeof(col));
    numc = 0;
    }
bool check(){
    for(int i = 1;i <= num;i++){
        int x = i << 1, y = i << 1 | 1;
        if(col[x << 1 | 1] == col[y << 1 | 1])return 0;
        }
    for(int i = 2;i <= (num << 1 | 1);i++){
        if(col[i << 1] == col[i << 1 | 1])return 0;
        }
    return 1;
    }
int main(){
    T = RD();
    while(T--){
        init();
        num = RD();nr = RD();
        char c;int x, y;
        for(int i = 1;i <= nr;i++){
            c = getchar();
            x = RD() * 2;
            if(c == 'm')x++;
            c = getchar();
            y = RD() * 2;
            if(c == 'm')y++;
            add(x << 1, y << 1 | 1, 1);
            add(y << 1, x << 1 | 1, 1);
            }
        for(int i = 1;i <= num;i++){
            int x = i * 2, y = i * 2 + 1;
            add(x << 1, y << 1 | 1, 1);
            add(y << 1, x << 1 | 1, 1);
            add(x << 1 | 1, y << 1, 1);
            add(y << 1 | 1, x << 1, 1);
            }
        for(int i = 4;i <= (num << 2) + 3;i++)if(!DFN[i])Tarjan(i);
        if(check())puts("GOOD");
        else puts("BAD");
        }
    return 0;
    }