Never or now.
本文从WordPress迁移而来, 查看全部WordPress迁移文章
2-sat模板题
判断是否存在可行解,建图后求强连通分量逐一判断所有对立点是否都在不同强连通分量
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;#define N 2010#define M 8000010 //2 * N * N#define cl memset#define pb push_backint n,tot,head[N];struct edge{ int v,next;}e[M];int dfn[N],low[N],belong[N],stack[N],dcnt,bcnt,top;bool ins[N];inline void add(int u ,int v){ e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;}void tarjan(int u){ dfn[u] = low[u] = ++dcnt; stack[++top] = u; ins[u] = true; for(int k = head[u]; k != -1; k = e[k].next){ int v = e[k].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]){ ++bcnt; while(true){ int x = stack[top--]; ins[x] = false; belong[x] = bcnt; if(x == u) break; } }}void scc(){ dcnt = bcnt = top = 0; cl(dfn,0,sizeof(dfn)); cl(ins,false,sizeof(ins)); for(int i = 0; i < 2*n; i++) if(!dfn[i]) tarjan(i);}int main(){ while(scanf("%d",&n)!=EOF){ int m; scanf("%d",&m); tot = 0; cl(head,-1,sizeof(head)); while(m--){ int x,y,fx,fy; scanf("%d%d%d%d",&x,&y,&fx,&fy); add((x<<1) + fx , (y<<1|1) - fy); add((y<<1) + fy , (x<<1|1) - fx); } scc(); bool res = true; for(int i = 0; i < n ; i++) if(belong[i<<1] == belong[i<<1|1]){ res = false; break; } if(res) puts("YES"); else puts("NO"); } return 0;}