先回顾最裸的2-sat模型
某国有n个党派，每个党派在议会中恰有2个代表。现在要成立和平委员会 ，该会满足：每个党派在和平委员会中有且只有一个代表 如果某两个代表不和，则他们不能都属于委员会 代表的编号从1到2n，编号为2a-1、2a的代表属于第a个党派。
思想： 由于一些人不能同时被选入委员会，那么假设a和b不和，那么当选泽a的时候必选择b’,当选择b的时候必选择a’.那么我们可以根据这个关系建个图。这个图是对称的，由于假如有边a->b’,那么必有b->a’.然后我们在这个图中找到答案，但是假如这个图中有环并且某个党派的的两个状态（人）都在里边，那么说明无解，否则说明有解。
再简化这个模型：就是有n个点，每个点有取与不取两种状态，m组矛盾，每一组矛盾为i和j，则i与jj要么都选要么都不选，ii与j要么都选要么都不选，在i于jj建立有向边，在j与ii建立有向边，这里注意一点：建图的时候是建立有向边，并且是对称建立。这里还有一点，为什么是i-〉jj，j-〉ii而不是ii->jj,jj->i，后面在具体解释。
注意三点：1、两种状态；2、矛盾是什么；3、边的意义
先看简单一些的poj 3207
http://poj.org/problem?id=3207
题目大意是：圆环上n个点编号为0,1,2,3......n-1，连接m组点，连线要么在圆内要么在圆外，判断线是否有相交。
线有两种状态：圆内与圆外，需要判断线是不是相交，可能相交的情况就两种（见代码），这时候建立的是双向边，我是这么理解的：line1,line2同时在圆内会相交，同时在圆外也会相交，那么就意味着如果line1在圆内，那么line2必须在圆外，如果line2在圆外，则line1必在圆内，所以建立双向边，下一个例子poj 3678你会看到并不是所有情况都可以建立双向边。line1在圆内的状态与line2在圆外的状态相连，line1在圆外的状态与line2在圆内的状态相连，最后检查矛盾，某一个line会不会在同一个强联通分量里
贴代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
#define N 1005
int head[N],scnt,cnt,dfn[N],low[N],id[N],n,m,ee[N][2];
struct node{
int to;
int next;
}edge[500000];
stack<int>st;
void addedge(int u,int v,int k)
{
edge[k].to=v;
edge[k].next=head[u];
head[u]=k;
}
void tarjan(int u)
{
int v,k,min1;
min1=dfn[u]=low[u]=cnt++;
st.push(u);
for(k=head[u];k!=-1;k=edge[k].next)
{
v=edge[k].to;
if(dfn[v]==-1)tarjan(v);
min1=min(min1,low[v]);
}
if(min1<low[u]){low[u]=min1;return;}
do
{
id[v=st.top()]=scnt;
st.pop();
low[v]=n;
}while(v!=u);
scnt++;
}
void init()
{
memset(dfn,-1,sizeof(dfn));
memset(head,-1,sizeof(head));
scnt=cnt=0;
}
int main()
{
int i,j,num;
scanf("%d%d",&n,&m);
init();
for(i=0;i<m;i++)
{
scanf("%d%d",&ee[i][0],&ee[i][1]);
if(ee[i][0]>ee[i][1])swap(ee[i][0],ee[i][1]);
}
num=0;
for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
{
if(ee[i][0]<ee[j][0]&&ee[j][0]<ee[i][1]&&ee[i][1]<ee[j][1]||ee[i][0]>ee[j][0]&&ee[i][0]<ee[j][1]&&ee[j][1]<ee[i][1])
{
addedge(i,j+m,num++);
addedge(j+m,i,num++);
addedge(j,i+m,num++);
addedge(i+m,j,num++);
}
}
for(i=0;i<m*2;i++)
if(dfn[i]==-1)tarjan(i);
bool flag=true;
for(i=0;i<m;i++)
{
if(id[i]==id[i+m]){flag=false;break;}
}
if(flag)printf("panda is telling the truth...\n");
else printf("the evil panda is lying again\n");
return 0;
}
在看难一些的poj 3678
题目似乎难以看懂，主要是那个万恶的表格难以看懂...
表格按高中学得表格看吧，其实就跟计算机本来的&,|,^是一样的，看不懂也没关系：
建图：
先找两种状态：第i个点是 0和1
再找矛盾：比如i&j=0,建立边i=1->j=0,j=1->i=0,这时候千万别写成双向边，因为i&j=0,只能说明如果i为1，j必须为0,不能说明如果j为0,i 必须为1(i取0也可以)，
注意不同。
比较难想的一点是，i&j=1，怎么建图，答案是建立边i=0->i=1,j=0->j=1
为什么？
看边的意义：i->j意味着如果i装态，则必有j状态，好了，i=0->i=1就意味着，i必定为1了
检查矛盾的方式还是那样，看矛盾的状态是不是在同一个强联通分量里，其实做了缩点处理
贴代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
#define N 2100
#define M 1000005
int head[N],dfn[N],low[N],id[N];
/*最后再来检查数组范围是不是够吧*/
int n,m,cnt,scnt;
stack<int>st;
struct node{
int to,next;
}edge[M*7];
void addedge(int u,int v,int k)
{
edge[k].to=v;
edge[k].next=head[u];
head[u]=k;
}
void tarjan(int u)
{
int v,i,min1=dfn[u]=low[u]=cnt++;
st.push(u);
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(dfn[v]==-1)tarjan(v);
min1=min(min1,low[v]);
}
if(min1<low[u]){low[u]=min1;return;}
do
{
id[v=st.top()]=scnt;
st.pop();
low[v]=n*2;
}while(v!=u);
scnt++;
}
void init()
{
memset(dfn,-1,sizeof(dfn));
memset(id,-1,sizeof(id));
memset(head,-1,sizeof(head));
scnt=cnt=0;
}
int main()
{
int i,j,a,b,c;
char op[4];
scanf("%d%d",&n,&m);
init();
int num=0;
for(i=0;i<m;i++)
{
scanf("%d%d%d%s",&a,&b,&c,op);
if(!strcmp(op,"AND"))
{
if(c==1)
{
addedge(a,a+n,num++);
addedge(b,b+n,num++);
addedge(a+n,b+n,num++);
addedge(b+n,a+n,num++);
}
else
{
addedge(a+n,b,num++);
addedge(b+n,a,num++);
}
}
else
if(!strcmp(op,"OR"))
{
if(c==0)
{
addedge(a+n,a,num++);
addedge(b+n,b,num++);
addedge(a,b,num++);
addedge(b,a,num++);
}
else
{
addedge(a,b+n,num++);
addedge(b,a+n,num++);
}
}
else
if(!strcmp(op,"XOR"))
{
if(c==0)
{
addedge(a,b,num++);
addedge(b,a,num++);
addedge(a+n,b+n,num++);
addedge(b+n,a+n,num++);
}
else
{
addedge(a,b+n,num++);
addedge(b+n,a,num++);
addedge(a+n,b,num++);
addedge(b,a+n,num++);
}
}
}
int flag=1;
for(i=0;i<n*2;i++)
if(dfn[i]==-1)tarjan(i);
for(i=0;i<n;i++)
{
if(id[i]==id[i+n]&&id[i]!=-1)
{
flag=0;
break;
}
}
if(flag)printf("YES\n");
else printf("NO\n");
while(!st.empty())st.pop();
return 0;
}
好奇一下，同样的代码交了两次，一次60多ms一次90多ms......数据自动生成计算量不同 那是不是一次tle 下一次rp好的话直接ac?值得一试 哈哈