2-sat问题主要解决的是一类二取一的问题.做法就是先建图,然后跑tarjan,然后就判断正负是否冲突,假如有冲突,就说明无解,否则就判断哪个的序号大...话说我也不知道为什么序号大就代表1.
题干:
题目背景 2-SAT 问题 模板 题目描述 有n个布尔变量x1x_1x1~xnx_nxn，另有m个需要满足的条件，每个条件的形式都是“xix_ixi为true/false或xjx_jxj为true/false”。比如“x1x_1x1为真或x3x_3x3为假”、“x7x_7x7为假或x2x_2x2为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。 输入输出格式 输入格式： 第一行两个整数n和m，意义如体面所述。 接下来m行每行4个整数 i a j b，表示“xix_ixi为a或xjx_jxj为b”(a,b∈{0,1}) 输出格式： 如无解，输出“IMPOSSIBLE”（不带引号）; 否则输出"POSSIBLE"（不带引号),下 一行n个整数x1x_1x1~xnx_nxn（xix_ixi∈{0,1}），表示构造出的解。 输入输出样例 输入样例#1： 复制 3 1 1 1 3 0 输出样例#1： 复制 POSSIBLE 0 0 0 说明 1<=n,m<=1e6 , 前3个点卡小错误，后面5个点卡效率，由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。
题解:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } struct node { int l,r,nxt; }a[4000014]; int lst[2000005],len = 0; void add(int x,int y) { a[++len].l = x; a[len].r = y; a[len].nxt = lst[x]; lst[x] = len; } int x,y,z,p,n,m,num = 0,ans = 0,top = 0; int low[2000005],stk[2000005],dfn[2000005],vis[2000005]; int col[2000005]; void tarjan(int u) { low[u] = dfn[u] = ++num; stk[++top] = u; vis[u] = 1; for(int k = lst[u];k;k = a[k].nxt) { int y = a[k].r; if(!dfn[y]) { tarjan(y); low[u] = min(low[u],low[y]); } else if(vis[y]) { low[u] = min(low[u],dfn[y]); } } if(low[u] == dfn[u]) { ans ++; int v; do { v = stk[top--]; vis[v] = 0; col[v] = ans; } while(u != v); } } int main() { read(n);read(m); int f1,f2; duke(i,1,m) { read(x);read(f1);read(y);read(f2); int k1,k2; k1 = f1 ^ 1; k2 = f2 ^ 1; add(x + k1 * n,y + f2 * n);//建边 add(y + k2 * n,x + f1 * n); } duke(i,1,2 * n) if(!dfn[i]) tarjan(i); int ok = 1; duke(i,1,n) { if(col[i] == col[i + n]) { ok = 0; printf("IMPOSSIBLE "); return 0; } } printf("POSSIBLE "); duke(i,1,n) { printf("%d ",col[i] > col[i + n]); } printf(" "); return 0; } /* 3 1 1 1 3 0 */