LightOJ 1251 Forming the Council(2-set入门)

2-set

• 定义: 有n个布尔变量(x_i)和m个形如(x_i = true/false || x_j = true /false)的条件,问能否为每个变量赋值使得,m个条件均被满足
• 解决: 对每个变量(x_i),拆成(2i和2i+1)两个点分别表示(x_i)为(false/true),最后对每个变量都设置一个赋值.

对于(x_i = true || x_j = false),在(2i和2j)建有向边((x_i)为假,则(x_j)一定为假),在(2j+1和2i+1)建有向边((x_j)为真则(x_i)一定为真)

求解时,我们考虑当前没有被赋值的变量(x_i),他只能为真/假,先假定他为假,在遍历后序所有的节点,如果能够全部赋值,则求解成功. 否则回退到当前(x_i),并令其为真,在进行一次遍历,若依然不成功,则问题无解

LightOj 1251

• 题意: 2-set裸题
• 思路: 对于 +1 +3 我们建如下两条边,其他情况同理
  

#include<bits/stdc++.h>
#define lson(p) (p<<1)
#define rson(p) (p<<1|1)
#define ll long long
using namespace std;
const int N = 1e5+10;

struct edge{
    int to,nxt;
}e[N*10];
int head[N],tot;
void init(){
    tot = 0;
    memset(head,0,sizeof head);
}
void add(int u,int v){
    e[++tot].to = v; e[tot].nxt = head[u]; head[u]=tot;
}
bool vis[N];
int S[N],top;

bool dfs(int u){
    if(vis[u^1])    return false;
    if(vis[u])  return true;
    vis[u] = true;
    S[top++] = u;
    for(int i=head[u];i;i=e[i].nxt){
        if(!dfs(e[i].to))   return false;
    }
    return true;
}

bool Twosat(int n){
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;i+=2){
        if(vis[i] || vis[i^1])  continue;
        top = 0;
        if(!dfs(i)){
            while(top) vis[S[--top]] = false;
            if(!dfs(i+1))  return false;
        }
    }
    return true;
}
vector<int> ans;
int main(){
    int n,m;
    int u,v;
    char op1,op2;
    int t;
    scanf("%d",&t);
    for(int _=1;_<=t;++_){
        init();
        ans.clear();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf(" %c%d %c%d",&op1,&u,&op2,&v);
            u--; v--;
            u *= 2 ;    v*=2;
            if(op1=='+')    u++;
            if(op2=='+')    v++;
// printf("%d %d %d %d
",u,v^1,v,u^1);
            add(v^1,u); add(u^1,v);
        }
        printf("Case %d: ",_);
        if(Twosat(m*2)){
            printf("Yes
");
            for(int i=0;i<m;i++){
                if(vis[i*2+1]){
                    ans.push_back(i);
                }
            }
            printf("%d",ans.size());
            for(auto i:ans){
                printf(" %d",i+1);
            }puts("");
        }else{
            printf("No
");
        }
    }
}