Preface
两道2-SAT模板题。
HDU3062
看题目就一眼2-SAT。一对夫妻看成一个变量，之间的矛盾可以看成限制。
考虑不同席的限制，相当于选了\(i\)就不选\(j\)，即必选\(j'\)。所以我们\(i\to j',j\to i'\)连边即可。
Tarjan判一发可行性即可。注意一下编号从\(0\)开始。
CODE
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
const int N=1005;
struct edge
{
int to,next;
}e[(N*N)<<1];
int head[N<<1],dfn[N<<1],low[N<<1],stack[N<<1],col[N<<1],n,m,cnt,tot,top,scc,x1,x2,y1,y2;
bool vis[N<<1];
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void Tarjan(int now)
{
dfn[now]=low[now]=++tot; stack[++top]=now; vis[now]=1;
for (register int i=head[now];~i;i=e[i].next)
if (!dfn[e[i].to]) Tarjan(e[i].to),low[now]=min(low[now],low[e[i].to]);
else if (vis[e[i].to]) low[now]=min(low[now],dfn[e[i].to]);
if (dfn[now]==low[now])
{
col[now]=++scc; vis[now]=0;
while (now!=stack[top])
col[stack[top]]=scc,vis[stack[top--]]=0; --top;
}
}
inline void clear(void)
{
memset(head,-1,sizeof(head)); memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis));
cnt=tot=top=scc=0;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; start:
while (scanf("%d%d",&n,&m)!=EOF)
{
for (clear(),i=1;i<=m;++i)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add((x1<<1)+x2,(y1<<1)+(!y2)); add((y1<<1)+y2,(x1<<1)+(!x2));
}
for (i=0;i<(n<<1);++i) if (!dfn[i]) Tarjan(i);
for (i=0;i<n;++i) if (col[i<<1]==col[(i<<1)+1]) { puts("NO"); goto start; }
puts("YES");
}
}
HDU1814
题目大意：现有\(n\)个党派，每个党派需要在两个代表中选一个，这\(2n\)个代表中有彼此讨厌的\(m\)对人，输出\(n\)个去开会的代表（多解则输出字典序最小解）
又是互相厌恶，这就很好办了，直接套上一题的建图方法，然后暴力DFS，中间清空标记。
字典序最小的话就优先选择\(i'\)，清空的时候不要ZZ一样的memset，开一个栈存一下递归到的点。
其他的都是板子。CODE
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
const int N=8005,M=20005;
struct edge
{
int to,next;
}e[M<<1];
int head[N<<1],stack[N<<1],n,m,x,y,top,cnt;
bool vis[N<<1];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline bool read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc())) if (ch==EOF) return 0;
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc())); return 1;
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline bool DFS(int now)
{
if (vis[now^1]) return 0;
if (vis[now]) return 1;
vis[now]=1; stack[top++]=now;
for (register int i=head[now];~i;i=e[i].next)
if (!DFS(e[i].to)) return 0;
return 1;
}
inline bool solve(void)
{
for (register int i=0;i<(n<<1);i+=2)
if (!vis[i]&&!vis[i^1])
{
top=0;
if (!DFS(i))
{
while (top) vis[stack[--top]]=0;
if (!DFS(i^1)) return 0;
}
}
return 1;
}
inline void print(void)
{
for (register int i=0;i<(n<<1);i+=2) printf("%d\n",vis[i]?i+1:(i^1)+1);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i;
while (read(n)&&read(m))
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for (cnt=0,i=1;i<=m;++i)
{
read(x); read(y); --x; --y;
add(x,y^1); add(y,x^1);
}
if (solve()) print(); else puts("NIE");
}
return 0;
}