加载中…
个人资料
暴风雪
暴风雪
  • 博客等级:
  • 博客积分:0
  • 博客访问:39,497
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

[2-sat]hdoj 4115:Eliminate the Conflict(2011 acm 成都现场赛E)

(2011-11-12 19:40:23)
标签:

hdoj

4115

eliminate

the

conflict

sat

成都

现场赛

acm

it

分类: 图论专区
大致题意:
     Alice和Bob要玩n局剪刀石头布, Alice已知Bob在n个回合中每一回合所出的类型(Bob好悲催!OIZ)。现在对于Alice有m个限制,每个限制由a,b,k三个数字来描述。如果k等于0,则代表第a局和第b局Alice必须出的相同。如果k==1,则代表第a局和第b局Alice必须出的不同。求是否存在可以使得Alice每局必胜且符合以上m个要求的方案。

大致思路:
    根据Bob在n局中出的类型先求出Alice为了每局都能够保证不输(包括平局)所可以选择出的类型(比如bob出石头,Alice就必须要出布或者是石头才能保证这一局不输)。然后根据m种要求,逐条分析第每条要求所包含的两局情况,建图后用2-sat判断即可。

详细代码:

#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=30015;
const int mMax=200000;

class edge{
public:
    int v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部

void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}

int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep;   //atype 强连通分量的个数
bool insta[nMax];
int n,m,b[nMax],rule[nMax][3],chose[nMax][2];

void Tarjan(int u){                 //我的Tarjan模版
    int i,j;
    dfn[u]=low[u]=++dep;
    sta[++top]=u;
    insta[u]=1;
    for(i=head[u];i;i=e[i].nex){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(insta[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        atype++;              //强连通分量个数
        do{
            j=sta[top--];
            belon[j]=atype;   //第j个点属于第type个连通块
            insta[j]=0;
        }while(u!=j);
    }
}

void init(){
    k=1;
    dep=1;
    top=atype=0;
    memset(insta,0,sizeof(insta)); //是否在栈中
    memset(head,0,sizeof(head));   //静态链表头指针
    memset(low,0,sizeof(low));     //Tarjan的low数组
    memset(dfn,0,sizeof(dfn));     //Tarjan的dfn数组
    memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}

bool judge(){
    for(int i=1;i<=n;i++){
        if(belon[i*2]==belon[i*2+1]){
            return 0;
        }
    }
    return 1;
}

int main(){
    int i,j,a1,a2,ia,t,cas=0;
    scanf("%d",&t);
    while(t--){
        cas++;
        scanf("%d%d",&n,&m);
        init();
        for(i=1;i<=n;i++){
            scanf("%d",&b[i]);
            if(b[i]==1){
                chose[i][0]=1;
                chose[i][1]=2;
            }
            if(b[i]==2){
                chose[i][0]=2;
                chose[i][1]=3;
            }
            if(b[i]==3){
                chose[i][0]=1;
                chose[i][1]=3;
            }
        }
        for(ia=1;ia<=m;ia++){
            scanf("%d%d%d",&rule[ia][0],&rule[ia][1],&rule[ia][2]);
            a1=rule[ia][0],a2=rule[ia][1];                  //a1 a2 所限制的两个回合
            if(rule[ia][2]==0){                             //如果必须相同的话
                if(chose[a1][0]==chose[a2][0]&&chose[a1][1]==chose[a2][1]){
                    addedge(2*a1,2*a2);
                    addedge(2*a2,2*a1);
                    addedge(2*a1+1,2*a2+1);
                    addedge(2*a2+1,2*a1+1);
                }
                else{                         //否则,肯定是一个相同,一个不同
                    for(i=0;i<2;i++){
                        for(j=0;j<2;j++){
                            if(chose[a1][i]==chose[a2][j]){
                                addedge(2*a1+i,2*a2+j);
                                addedge(2*a2+j,2*a1+i);
                                addedge(2*a1+1-i,2*a1+i);
                                addedge(2*a2+1-j,2*a2+j);
                            }
                        }
                    }
                }
            }
            else{                                                  //如果必须不同的话
                if(chose[a1][0]==chose[a2][0]&&chose[a1][1]==chose[a2][1]){
                    addedge(2*a1,2*a2+1);
                    addedge(2*a2,2*a1+1);
                    addedge(2*a1+1,2*a2);
                    addedge(2*a2+1,2*a1);
                }
                else{                        //否则,肯定是一个相同,一个不同
                    for(i=0;i<2;i++){
                        for(j=0;j<2;j++){
                            if(chose[a1][i]==chose[a2][j]){
                                addedge(2*a1+i,2*a2+1-j);
                                addedge(2*a2+j,2*a1+1-i);
                            }
                        }
                    }
                }
            }
        }
        for(i=1;i<=2*n+1;i++){
            if(!dfn[i])Tarjan(i);
        }
        printf("Case #%d: ",cas);
        if(judge()){
            printf("yes\n");
        }
        else{
            printf("no\n");
        }
    }
    return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有