[BZOJ1823/Luogu4171][JSOI2010]满汉全席(2-sat,Tarjan)

发布于 2018-05-28  187 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1823/Luogu4171][JSOI2010]满汉全席(2-sat,Tarjan)

Description

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

Tag

2-sat,Tarjan

解决思路

由于每一种食材只能选择制作汉式或满式的一种,同时又有\(m\)组如果选择不制作某种食物就必须制作另一种的限制,所以是一个经典的\(2-sat\)模型,建立\(4n\)个点分别连边,然后\(Tarjan\)缩点判断是否矛盾。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101*4;
const int maxM=maxN*maxN*4;
const int inf=2147483647;

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int top=0,Stack[maxN];
bool instack[maxN];
int idcnt=0,Id[maxN];
int dfncnt,dfn[maxN],low[maxN];

void Add_Edge(int u,int v);
void tarjan(int u,int fa);

int main()
{
    int TTT;scanf("%d",&TTT);
    while (TTT--)
    {
        scanf("%d%d",&n,&m);
        edgecnt=0;mem(Head,-1);dfncnt=0;mem(dfn,0);top=0;mem(instack,0);
        for (int i=1;i<=n;i++) Add_Edge(i,i+n*3),Add_Edge(i+n*3,i),Add_Edge(i+n,i+n*2),Add_Edge(i+n*2,i+n);
        for (int i=1;i<=m;i++)
        {
            int id1,id2;
            char opt1,opt2;
            scanf("\n%c%d %c%d",&opt1,&id1,&opt2,&id2);
            int d1=((opt1=='h')?(0):(n)),d2=((opt2=='h')?(0):(n));
            Add_Edge(id1+2*n+d1,id2+d2);Add_Edge(id2+2*n+d2,id1+d1);
        }
        for (int i=1;i<=n*4;i++)
            if (dfn[i]==0) tarjan(i,0);

        bool flag=1;
        for (int i=1;i<=2*n;i++) if (Id[i]==Id[i+2*n]) flag=0;
        printf("%s\n",(flag)?("GOOD"):("BAD"));
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++dfncnt;
    instack[u]=1;Stack[++top]=u;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (dfn[V[i]]==0)
        {
            tarjan(V[i],u);
            low[u]=min(low[u],low[V[i]]);
        }
        else if (instack[V[i]]) low[u]=min(low[u],dfn[V[i]]);
    if (dfn[u]==low[u])
    {
        int v;idcnt++;
        do v=Stack[top--],instack[v]=0,Id[v]=idcnt;
        while (u!=v);
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1823/Luogu4171][JSOI2010]满汉全席(2-sat,Tarjan)


HNCJ OIer