首页 > 其他 > 详细

poj3678:Katu Puzzle——题解

时间:2017-11-18 10:23:29      阅读:234      评论:0      收藏:0      [点我收藏+]

http://poj.org/problem?id=3678

总觉得这题比例题简单。

a为x取0的点,a+n为x取1的点。

我们还是定义a到b表示取a必须取b。

那么我们有:

当AND:

1.当c=1:add(a,a+n); add(b,b+n);//我们不能取0的点,所以我们让程序一旦取0必会矛盾,下面类似的同理。

2.当c=0:add(a+n,b); add(b+n,a);

当OR

1.当c=1:add(a,b+n);add(b,a+n);

 

2.当c=0:add(a+n,a);add(b+n,b);

当OR

1.当c=1:add(a+n,b);add(b+n,a);add(a,b+n); add(b,a+n);

 

 2.当c=0:add(a+n,b+n);add(b+n,a+n);add(a,b);add(b,a);

剩下的就是2-SAT(tarjan缩点)的活了。

#include<stack>
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,w=1;char ch=0;
    while(ch<0||ch>9){if(ch==-)w=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=(x<<1)+(x<<3)+ch-0;ch=getchar();}
    return x*w;
}
const int N=10001;
const int M=1000005;
struct node{
    int to;
    int nxt;
}edge[M*4];
int head[N],dfn[N],low[N],to[N];
int n,m,t,l,cnt;
bool instack[N*4];
stack<int>q;
inline void add(int u,int v){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void tarjan(int u){
    t++;
    dfn[u]=t;
    low[u]=t;
    q.push(u);
    instack[u]=1;
    for(int i=head[u];i!=0;i=edge[i].nxt){
    int v=edge[i].to;
    if(!dfn[v]){
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }else if(instack[v]){
        low[u]=min(low[u],dfn[v]);
    }
    }
    if(low[u]==dfn[u]){
    int v;
    l++;
    do{
        v=q.top();
        q.pop();
        instack[v]=0;
        to[v]=l;
    }while(v!=u);
    }
    return;
}
//a为x取0的点,a+n为x取1的点
int main(){
    int n=read();
    int m=read();
    for(int i=1;i<=m;i++){
    int a=read();
    int b=read();
    int c=read();
    char op[5];
    scanf("%s",op);
    if(op[0]==A){
        if(c){
        add(a,a+n);
        add(b,b+n);
        }else{
        add(a+n,b);
        add(b+n,a);
        }
    }
    if(op[0]==O){
        if(c){
        add(a,b+n);
        add(b,a+n);
        }else{
        add(a+n,a);
        add(b+n,b);
        }
    }
    if(op[0]==X){
        if(c){
        add(a+n,b);
        add(b+n,a);
        add(a,b+n);
        add(b,a+n);
        }else{
        add(a+n,b+n);
        add(b+n,a+n);
        add(a,b);
        add(b,a);
        }
    }
    }
    for(int i=0;i<n*2;i++){
    if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<n;i++){
    if(to[i]==to[i+n]){
        printf("NO\n");
        return 0;
    }
    }
    printf("YES\n");
    return 0;
}

 

poj3678:Katu Puzzle——题解

原文:http://www.cnblogs.com/luyouqi233/p/7855940.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!