关闭

BZOJ1823 [JSOI2010]满汉全席 【2-sat】

288人阅读 评论(0) 收藏 举报
分类:

题目

满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在數量繁多的菜色之中。由于菜色众多而繁杂,只有极少數博学多闻技艺高超的厨师能够做出满汉全席,而能够烹饪出经过专家认证的满汉全席,也是中国厨师最大的荣誉之一。 世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成,而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会,将于近日举办满汉全席大赛,协会派遣许多会员当作评审员,为的就是要在參赛的厨师之中,找到满汉料理界的明日之星。 大会的规则如下:每位參赛的选手可以得到n 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。大会的评审制度是:共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解,但基本见解是,要有兩样菜色作为满汉全席的标志。如某评审认为,如果没有汉式东坡肉跟满式的涮羊肉锅,就不能算是满汉全席。但避免过于有主見的审核,大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下,才能淘汰一位选手,否则不能淘汰一位參赛者。换句话說,只要參赛者能在这兩种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉,羊肉和牛肉时,有四位评审员的喜好如下表: 评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉 如參赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而參赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理,就可以满足所有评审的要求。 但大会后來发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的參赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时,则不論參赛者采取什么样的做法,都不可能通过所有评审的考核: 评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉 所以大会希望有人能写一个程序來判断,所选出的m 位评审,会不会发生 没有人能通过考核的窘境,以便协会组织合适的评审团。

输入格式

第一行包含一个数字 K,代表测试文件包含了K 组资料。每一组测试资料的第一行包含兩个数字n 跟m(n≤100,m≤1000),代表有n 种材料,m 位评审员。为方便起見,材料舍弃中文名称而给予编号,编号分别从1 到n。接下來的m 行,每行都代表对应的评审员所拥有的兩个喜好,每个喜好由一个英文字母跟一个数字代表,如m1 代表这个评审喜欢第1 个材料透过满式料理做出來的菜,而h2 代表这个评审员喜欢第2 个材料透过汉式料理做出來的菜。每个测试文件不会有超过50 组测试资料

输出格式

每笔测试资料输出一行,如果不会发生没有人能通过考核的窘境,输出GOOD;否则输出BAD(大写字母)。

输入样例

2

3 4

m3 h1

m1 m2

h1 h3

h3 m2

2 4

h1 m2

m2 m1

h1 h2

m1 h2

输出样例

GOOD

BAD

题解

一句话题意:

有n个物品,每个物品赋予’h’或’m’一种属性。有m个二元限制:“某物品必须是某属性”,要求每个二元限制至少满足一个,问是否有解

经典的2-sat问题,是一个入门题【都不用输出方案。。。】
对于每个限制,我们如果不选第一个就必须选第二个
我们把物品分为两个点分别表示两种属性。显然一个物品不能同时具有两个属性,所以它们是互斥的。对于每对限制,两个点分别向另一个点的相对点连有向边,2-sat判断一下就好

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 205,maxm = 100005,INF = 1000000000;
inline int RD(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
    return out * flag;
}
int get(){
    char c = getchar();
    while (c != 'm' && c != 'h') c = getchar();
    return 2 * RD() - (c == 'h');
}
int n,m,h[maxn],ne = 0;
struct EDGE{int to,nxt;}ed[maxm];
inline void build(int u,int v){
    ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
}
int dfn[maxn],low[maxn],Scc[maxn],scci,cnt,st[maxn],top = 0;
void dfs(int u){
    dfn[u] = low[u] = ++cnt;
    st[++top] = u;
    Redge(u){
        if (!dfn[to = ed[k].to])
            dfs(to),low[u] = min(low[u],low[to]);
        else if (!Scc[to]) low[u] = min(low[u],dfn[to]);
    }
    if (dfn[u] == low[u]){
        scci++;
        do{Scc[st[top]] = scci;}while (st[top--] != u);
    }
}
int main(){
    int T = RD(),x,y,u,v,flag;
    while (T--){
        n = RD(); m = RD(); flag = true;
        ne = scci = cnt = 0;
        REP(i,n << 1) dfn[i] = h[i] = Scc[i] = 0;
        while (m--){
            x = get(); y = get();
            u = (x & 1) ? x + 1 : x - 1;
            v = (y & 1) ? y + 1 : y - 1;
            build(x,v); build(y,u);
        }
        REP(i,n << 1) if (!dfn[i]) dfs(i);
        REP(i,n) if (Scc[2 * i] == Scc[2 * i - 1]){flag = false; break;}
        if (flag) puts("GOOD");
        else puts("BAD");
    }
    return 0;
}
0
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

算法基础 - 2-sat问题

2-SAT问题这个问题其实我们平时早就遇到过,只是从来没有认真的去思考这个问题的解法。这个在我们理解的时候,一般都是按照一个点开始,可以就继续,不可以就停止。例子问题例如我们有10个球,每个球都是编号...
  • chenfs1992
  • chenfs1992
  • 2016-05-30 22:03
  • 1547

【研究总结】2-sat问题

序言            最近花了一点心思研究2-sat模型,看了很多论文博客等等,也在POJ上做了一点题。其实这个东西也还挺好玩的,当然,前提是每道题你都有认真分析,认真想清楚模型的意义,搞明...
  • JarjingX
  • JarjingX
  • 2013-01-20 11:23
  • 10387

关于2-sat的建图方法及解决方案

-------------------------------------------------对于2-sat问题的描述---------------------------------------...
  • qq_24451605
  • qq_24451605
  • 2015-07-29 14:23
  • 1924

BZOJ 1823 JSOI 2010 满汉全席 2-SAT

题目大意:有n种材料,m个评委。每种材料有两种不同的做法,每个评委有两个判定标准,做出来的菜品必须满足每一个评委至少一个要求。问有没有这样的方案。 思路:2-SAT经典建图问题。因为每一种材...
  • jiangyuze831
  • jiangyuze831
  • 2014-10-02 09:40
  • 899

【bzoj1823】【jsoi2010】【满汉全席】【2-sat】

Description 满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在數量繁多的菜色之中。由于菜色众多而繁杂,只有极少數博学多闻技艺高超的厨师能够做出满汉全...
  • sunshinezff
  • sunshinezff
  • 2015-10-26 17:17
  • 282

[BZOJ1823][JSOI2010]满汉全席(2-SAT)

哈哈哈Loli今天终于不考试了
  • FromATP
  • FromATP
  • 2017-04-05 07:35
  • 275

bzoj 1823 [JSOI2010]满汉全席

bzoj 1823 【jsoi2010】满汉全席 题解
  • unicornt_
  • unicornt_
  • 2016-07-16 07:48
  • 239

BZOJ 1823 [JSOI2010] 满汉全席

2-SAT
  • SenyeLicone
  • SenyeLicone
  • 2017-07-08 11:47
  • 196

[BZOJ1823][JSOI2010]满汉全席 做题笔记

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1823我做的第一道2-SAT裸题。不得不说题目描述看起来比NOI2002银河英雄传说都可怕。...
  • mhlwsk
  • mhlwsk
  • 2016-03-07 18:38
  • 432

[BZOJ 1823] 满汉全席 2-SAT

题目传送门:【BZOJ 1823】题目大意: ……为了招收新进的厨师进入世界满汉全席协会,近日该协会将举办满汉全席大赛。协会将派遣许多会员当作评委,为的就是要在参赛的厨师之中,找到满汉料理界的明日之星...
  • ArcCCcp
  • ArcCCcp
  • 2017-08-10 00:13
  • 130
    个人资料
    • 访问:14541次
    • 积分:2221
    • 等级:
    • 排名:第19517名
    • 原创:208篇
    • 转载:0篇
    • 译文:0篇
    • 评论:13条
    联系方式
    QQ:976776104 添加注明省份昵称什么的就最好了OvO
    最新评论