首页 > 其他 > 详细

BZOJ 2199: [Usaco2011 Jan]奶牛议会 2- SAT

时间:2018-06-20 18:07:33      阅读:173      评论:0      收藏:0      [点我收藏+]

2199: [Usaco2011 Jan]奶牛议会

Description

由于对Farmer John的领导感到极其不悦,奶牛们退出了农场,组建了奶牛议会。议会以“每头牛 都可以获得自己想要的”为原则,建立了下面的投票系统: M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) 。每只 奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投 出“是”或“否”(输入文件中的‘Y‘和‘N‘)。他们的投票结果分别为VB_i (VB_i in {‘Y‘, ‘N‘}) and VC_i (VC_i in {‘Y‘, ‘N‘})。 最后,议案会以如下的方式决定:每只奶牛投出的两票中至少有一票和最终结果相符合。 例如Bessie给议案1投了赞成‘Y‘,给议案2投了反对‘N‘,那么在任何合法的议案通过 方案中,必须满足议案1必须是‘Y‘或者议案2必须是‘N‘(或者同时满足)。 给出每只奶牛的投票,你的工作是确定哪些议案可以通过,哪些不能。如果不存在这样一个方案, 输出"IMPOSSIBLE"。如果至少有一个解,输出: Y 如果在每个解中,这个议案都必须通过 N 如果在每个解中,这个议案都必须驳回 ? 如果有的解这个议案可以通过,有的解中这个议案会被驳回 考虑如下的投票集合: - - - - - 议案 - - - - - 1 2 3 奶牛 1 YES NO 奶牛 2 NO NO 奶牛 3 YES YES 奶牛 4 YES YES 下面是两个可能的解: * 议案 1 通过(满足奶牛1,3,4) * 议案 2 驳回(满足奶牛2) * 议案 3 可以通过也可以驳回(这就是有两个解的原因) 事实上,上面的问题也只有两个解。所以,输出的答案如下: YN?

Input

* 第1行:两个空格隔开的整数:N和M * 第2到M+1行:第i+1行描述第i只奶牛的投票方案:B_i, VB_i, C_i, VC_i

Output

* 第1行:一个含有N个字符的串,第i个字符要么是‘Y‘(第i个议案必须通过),或者是‘N‘ (第i个议案必须驳回),或者是‘?‘。 如果无解,输出"IMPOSSIBLE"。

Sample Input


3 4
1 Y 2 N
1 N 2 N
1 Y 3 Y
1 Y 2 Y


Sample Output

YN?

思路:

  2-SAT 裸题, 对于每个要求, 我们把非x和y , 非y和x 连一条边,然后枚举每个点的两种情况进行bfs染色,由连边可知,bfs染色后会满足所有情况,若某个点既选又不选,则这种情况不可能。近似暴力的一道题。

技术分享图片
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5000, M = 10000;
int head[N], to[M], nxt[M], _; 
char ans[N];
bool vis[N];
void add(int a,int b) {
    to[++_] = b;
    nxt[_]  = head[a];
    head[a] = _;
}
int n, m;
queue<int>q;
bool bfs(int s) {
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    while(!q.empty())q.pop();
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            if(!vis[to[i]]) {
                vis[to[i]] = 1;
                q.push(to[i]);
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(vis[i]&&vis[n+i]) return 0;
    }
    return 1;
}
int main() {
    scanf("%d%d", &n, &m);
    char s1[3], s2[3];
    for(int i=1, x, y;i<=m;i++) {
        scanf("%d%s%d%s", &x, s1, &y, s2);
        int tx, ty;
        if(s1[0]==Y) tx = 1;else tx = 0;
        if(s2[0]==Y) ty = 1;else ty = 0;
        add((1-tx)*n+x,ty*n+y);
        add((1-ty)*n+y,tx*n+x);
    }
    for(int i=1;i<=n;i++) {
        int t = bfs(i+n), f = bfs(i);
        if(!t&&!f) {
            puts("IMPOSSIBLE");
            return 0;
        }
        if(t&&f) ans[i] = ?;
        else if(!f) ans[i] = Y;
        else if(!t) ans[i] = N;
    }
    for(int i=1;i<=n;i++) {
        putchar(ans[i]);
    }
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5000, M = 10000;
int head[N], to[M], nxt[M], _; 
char ans[N];
bool vis[N];
void add(int a,int b) {
    to[++_] = b;
    nxt[_]  = head[a];
    head[a] = _;
}
int n, m;
queue<int>q;
bool bfs(int s) {
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    while(!q.empty())q.pop();
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            if(!vis[to[i]]) {
                vis[to[i]] = 1;
                q.push(to[i]);
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(vis[i]&&vis[n+i]) return 0;
    }
    return 1;
}
int main() {
    scanf("%d%d", &n, &m);
    char s1[3], s2[3];
    for(int i=1, x, y;i<=m;i++) {
        scanf("%d%s%d%s", &x, s1, &y, s2);
        int tx, ty;
        if(s1[0]==Y) tx = 1;else tx = 0;
        if(s2[0]==Y) ty = 1;else ty = 0;
        add((1-tx)*n+x,ty*n+y);
        add((1-ty)*n+y,tx*n+x);
    }
    for(int i=1;i<=n;i++) {
        int t = bfs(i+n), f = bfs(i);
        if(!t&&!f) {
            puts("IMPOSSIBLE");
            return 0;
        }
        if(t&&f) ans[i] = ?;
        else if(!f) ans[i] = Y;
        else if(!t) ans[i] = N;
    }
    for(int i=1;i<=n;i++) {
        putchar(ans[i]);
    }
}
View Code

 

BZOJ 2199: [Usaco2011 Jan]奶牛议会 2- SAT

原文:https://www.cnblogs.com/Tobichi/p/9204472.html

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