noip之前学的内容了，看到题竟然忘了怎么建图了，复习一下。
2-sat
大概是对于每个元素，它有0和1两种选择，必须选一个但不能同时选。这之间又有一些二元关系，比如x&y=1等等。。。
先把每个点拆成0和1两个点。
那么我们就建图，如果x等于A的话y必须等于B，那么从x的A点向y的B点连一条有向边，表示选了一个点它所有的后继点也必须选。
没有一组合法解的情况当且仅当x的01两个点缩点后在同一个强联通分量里。
bzoj 1823
裸题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 205
#define M 4005
using namespace std;
int n,m;
int head[N],ver[M],nxt[M],tot;
void add(int a,int b)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
int dfn[N],low[N],tim,in[N],st[N],top,cnt,be[N];
void dfs(int x)
{
dfn[x]=low[x]=++tim;
st[++top]=x;
in[x]=;
for(int i=head[x];i;i=nxt[i])
{
if(!dfn[ver[i]])
{
dfs(ver[i]);
low[x]=min(low[x],low[ver[i]]);
}
else if(in[ver[i]])
{
low[x]=min(low[x],dfn[ver[i]]);
}
}
if(low[x]==dfn[x])
{
cnt++;int y;
do
{
y=st[top--];
be[y]=cnt;
in[y]=;
}while(y!=x);
}
return ;
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
tim=tot=cnt=top=;
memset(be,,sizeof(be));
memset(head,,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
scanf("%d%d",&n,&m);
char s1[],s2[];
for(int i=;i<=m;i++)
{
scanf("%s%s",s1,s2);
int k1,k2;k1=k2=;
int len1=strlen(s1);
for(int i=;i<len1;i++)
{
k1=k1*+s1[i]-'';
}
int len2=strlen(s2);
for(int i=;i<len2;i++)
{
k2=k2*+s2[i]-'';
}
int op1,op2;
if(s1[]=='m')op1=;else op1=;
if(s2[]=='m')op2=;else op2=;
add(k1+(op1^)*n,k2+op2*n);
add(k2+(op2^)*n,k1+op1*n);
}
for(int i=;i<=*n;i++)if(!dfn[i])dfs(i);
bool flag=;
for(int i=;i<=n;i++)if(be[i]==be[i+n])flag=;
if(flag)puts("BAD");
else puts("GOOD");
}
return ;
}
bzoj 2199
按2-sat建完图之后，从每个点开始dfs一遍。
如果一个点能访问到它的对立点说明这个点不能选。
如果x的两个点都不能选说明无解，相当于在同一个强联通分量里。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2005
#define M 8005
using namespace std;
int n,m;
int head[N],ver[M],nxt[M],tot;
void add(int a,int b)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
int ans[N];
int v[N];
void dfs(int x)
{
v[x]=;
for(int i=head[x];i;i=nxt[i])
{
if(!v[ver[i]])dfs(ver[i]);
}
}
int main()
{
scanf("%d%d",&n,&m);
char s1[],s2[];
int t1,t2;
for(int i=;i<=m;i++)
{
scanf("%d",&t1);scanf("%s",s1);
scanf("%d",&t2);scanf("%s",s2);
int op1,op2;
if(s1[]=='Y')op1=;else op1=;
if(s2[]=='Y')op2=;else op2=;
add(t1+(op1^)*n,t2+op2*n);
add(t2+(op2^)*n,t1+op1*n);
}
bool flag=;
for(int i=;i<=n;i++)
{
int now=;
memset(v,,sizeof(v));
dfs(i);
if(v[i+n])now++;
memset(v,,sizeof(v));
dfs(i+n);
if(v[i])now+=;
ans[i]=now;
if(now==)flag=;
}
if(flag)puts("IMPOSSIBLE");
else
{
for(int i=;i<=n;i++)
{
if(!ans[i])putchar('?');
else if(ans[i]==)putchar('Y');
else putchar('N');
}
}
return ;
}