POJ3207 Ikki's Story IV

开始学习2-sat的姿势

http://blog.csdn.net/jarjingx/article/details/8521690

这篇文章写的真好

算法的过程如下：
构图
　　更具体的后面再说
缩点
　　Tarjan算法缩点，将所有的边反过来（为什么？后面有嗯）
判可行
　　枚举集合的两个元素，看其是否处于不同的块内，若否的话则给出不可行信息
记录矛盾
　　这里所说的矛盾不是题中给出的两个人之间有仇恨，那样的边是实际存在，我们这里说的矛盾是指若两个块分别含有两个对立节点，也就是说一个集合的两个元素分布在了两个不同的块中，那么这两个块就是矛盾的，即不可能同时被选择，这样一种矛盾关系是不存在于边中的，是不依赖于输入的数据的，我们要找到与一个块对立的块，并把它们保存下来。
拓扑排序
　　将缩点后的图进行拓扑排序（排的是块而不是节点）
构造方案
　　按照拓扑序列的顺序，依次访问所有块，若一个块未被标记，将其标记为“选择”，不传递“选择”标记，将被选块的对立块标记为“不选择”，将其“不选择”标记沿着边正向传递。（不是逆着边么？哼，图已经被反过来了，你到底有没有认真看呐！囧）

本题建图判断即可

By：大奕哥

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int low[N],vis[N],dfn[N],n,m,cnt,ccnt,num,head[N],s[N],top,col[N];
struct node{
    int x,y;
}p[N];
struct edge
{
    int to,nex;
}e[N<<2];
void add(int x,int y)
{
    e[++ccnt].to=y;e[ccnt].nex=head[x];head[x]=ccnt;
}
void dfs(int x)
{
    s[++top]=x;
    vis[x]=1;dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=e[i].nex)
    {
        int y=e[i].to;
        if(!dfn[y]){
            dfs(y);
            low[x]=min(low[y],low[x]);
        }
        else if(vis[y]){
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x])
    {
        num++;
        while(s[top+1]!=x){
            int a=s[top--];
            vis[a]=0;
            col[a]=num;
        }
    }
    return;
}
void tarjan()
{
    cnt=num=top=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(col,0,sizeof(col));
    for(int i=1;i<=m*2;++i)
    if(!dfn[i])dfs(i);
}
bool solve()
{
    tarjan();
    for(int i=1;i<=m;++i)if(col[i]==col[i+m])return 0;
    return 1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        ccnt=0;memset(head,0,sizeof(head));int x,y;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            if(x>y)swap(x,y);
            p[i].x=x;p[i].y=y;
        }
        for(int i=1;i<=m;++i)
        for(int j=i+1;j<=m;++j){
            if(p[j].x>=p[i].x&&p[j].x<=p[i].y&&p[i].y<=p[j].y||
            p[j].x<=p[i].x&&p[i].x<=p[j].y&&p[j].y<=p[i].y)
            {
                add(i,j+m);add(i+m,j);
                add(j,i+m);add(j+m,i);
            }
        }
        if(solve())puts("panda is telling the truth...");
        else puts("the evil panda is lying again");
    }
    return 0;
}

POJ3207 Ikki's Story IV

相关推荐