飞机票：http://poj.org/problem?id=3678

分析：题意。。。就是说给你个有向图，然后给你变a b 且a b有个值为c 要求a的值op b的值=c 其中op为（&，|，^）位运算，求解是否可以求出这样的解。继续2-sat。。。这题怎么搞呢。。。其实只要知道为位运算相互间的限制然后建图求解即可。。。那么关系是什么呢。。。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了

AND 结果为1：建边 x*2+1->x*2,y*2+1->y*2 （两个数必须全为1）

AND 结果为0：建边 y*2->x*2+1,x*2->y*2+1 （两个数至少有一个为0）

OR 结果为1：建边 x*2+1->y*2,2*y+1->x*2 （两个数至少有一个为1）

OR 结果为0：建边 x*2->x*2+1,y*2->y*2+1 （两个数必须全为0）

XOR 结果为1：建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 （两个数必须不同）

XOR 结果为0：建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 （两个数必须相同）

然后建边就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=2345;
vector<int> V[maxn];
int n,m;
char ch[100];
void init()
{
    for(int i=0; i<=2*n; i++)V[i].clear();
    int u,v,c;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%s",&u,&v,&c,ch+1);
        u=u*2;
        v=v*2;
        if(ch[1]=='A')
        {
            if(c==0)
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
            }
            else
            {
                V[u^1].push_back(u);
                V[v^1].push_back(v);
            }
        }
        else if(ch[1]=='O')
        {
            if(c==0)
            {
                V[u].push_back(u^1);
                V[v].push_back(v^1);
            }
            else
            {
                V[u^1].push_back(v);
                V[v^1].push_back(u);
            }
        }
        else
        {
            if(c==0)
            {
                V[u].push_back(v);
                V[v].push_back(u);
                V[u^1].push_back(v^1);
                V[v^1].push_back(u^1);
            }
            else
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
                V[v^1].push_back(u);
                V[u^1].push_back(v);
            }

        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*n; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<n; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://poj.org/problem?id=3207

分析：题目有点难懂。。。但还是2-sat 。。题目的意思就是按顺时针给定圆上n个点。标号0~n-1.然后m个连接。。。注意：连接可以连接在圆内也可以在圆外。。。这里提示我们不一定是直线。。。然后判断是否可以不相交在圆内或圆外。。可以相交在圆上。。。

题目都看晕了。。。其实很简单。。。假如当前是的i个连接且坐标为li ri,如果有个连接k。且lk>li&&lk<ri&&rk>ri 或则

rk>li&&rk<lr&&lk<li 这样就代表这两条不能在一侧。否则相交。。画个图你就懂了

这里有个判断我很喜欢

  int cnt=0;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;

如果cnt=1就相交。。。为什么呢cnt=1时就说明前面满足了一个条件。另一个不满足。。就是说只有一个点在里面。另个在外面。。怎么画肯定都相交。。。简单易懂。。然后就是2-sat 啪啪啪~~~oh，no！好像还有个问题。。就是这里要添加4条边。。因为互相制约。。然后就可以AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,m;
struct he
{
    int l,r;
} JLJ[567];
void init()
{
    for(int i=0; i<=2*m; i++)V[i].clear();
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        if(u>v)swap(u,v);
        JLJ[i].l=u;
        JLJ[i].r=v;
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=i+1; j<=m; j++)
        {
            int cnt=0;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;
            if(cnt==1)
            {
                int u=2*(i-1);
                int v=2*(j-1);
                V[u].push_back(v+1);
                V[u+1].push_back(v);
                V[v].push_back(u+1);
                V[v+1].push_back(u);
            }
        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*m; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<m; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("the evil panda is lying again\n");
            return;
        }
    }
    printf("panda is telling the truth...\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}