首页 > 其他 > 详细

[BZOJ 2199] 奶牛议会

时间:2018-08-29 19:35:28      阅读:167      评论:0      收藏:0      [点我收藏+]

[题目链接]

         https://www.lydsy.com/JudgeOnline/problem.php?id=2199

[算法]

       2-SAT

[代码]

        

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
#define MAXM 4010

struct edge
{
        int to,nxt;
} e[MAXM << 1];
int n,m,tot;
int head[MAXN << 1];
bool visited[MAXN << 1];

inline void addedge(int u,int v)
{
        tot++;
        e[tot] = (edge){v,head[u]};
        head[u] = tot;
}
inline void dfs(int x)
{
        for (int i = head[x]; i; i = e[i].nxt)
        {
                if (!visited[e[i].to])
                {
                        visited[e[i].to] = true;
                        dfs(e[i].to);
                }
        }
}
inline bool ok(int x)
{
        for (int i = 1; i <= 2 * n; i++) visited[i] = false;
        visited[x] = true;
        dfs(x);
        for (int i = 1; i <= n; i++)
        {
                if (visited[i] && visited[i + n])
                        return false;
        }
        return true;
}

int main() 
{
        
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= m; i++)
        {
                int b,c;
                char vb[2],vc[2];
                scanf("%d%s%d%s",&b,&vb,&c,&vc);
                if (vb[0] == Y && vc[0] == Y)
                {
                        addedge(b + n,c);
                        addedge(c + n,b);
                }
                if (vb[0] == Y && vc[0] == N)
                {
                        addedge(b + n,c + n);
                        addedge(c,b);
                }
                if (vb[0] == N && vc[0] == Y)
                {
                        addedge(b,c);
                        addedge(c + n,b + n);
                }
                if (vb[0] == N && vc[0] == N)
                {
                        addedge(b,c + n);
                        addedge(c,b + n);
                }
        }
        for (int i = 1; i <= n; i++)
        {
                bool x = ok(i) , y = ok(i + n);
                if (!x && !y)
                {
                        printf("IMPOSSIBLE\n");
                        return 0;        
                } 
                if (x && !y)
                {
                        printf("Y");
                        continue;
                }
                if (!x && y)
                {
                        printf("N");
                        continue; 
                }
                if (x && y)
                {
                        printf("?");
                        continue;
                }
        }
        printf("\n");
        
        return 0;
    
}

 

[BZOJ 2199] 奶牛议会

原文:https://www.cnblogs.com/evenbao/p/9556352.html

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