「Luogu P4171」[JSOI2010]满汉全席

发表于 |
字数统计: 677 | 阅读时长 ≈ 3

有$n$种食材和$m$位评委。每一位选手要将$n$种食材全部做成满式或汉式料理。如果一位选手做出的菜符合每位评委所喜好的两种菜品中的一种，那么说这位选手是通过考核的。

一共有$T$组数据，对于每组数据，给定$m$位评委所喜好的菜品，问是否有一种做法，使得能通过考核。

$\texttt{Data Range:}T\leq 10,n\leq 100,m\leq 1000$

链接

Luogu P4171

BZOJ 1823

题解

设$x_i$为$[$第$i$种食材做汉式$]$，那么评委的限制就变成$x_i$为真或者$x_j$为假这样的形式了。

于是，可以把题意转换成是否存在一组$x_i$的取值，使得这些取值能满足所有约束条件。

这就是个$\texttt{2-SAT}$的板子题了。

唯一需要注意的是多组数据记得清零！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e4+51;
struct Edge{
    ll to,prev;
};
Edge ed[MAXN<<1];
stack<ll>st;
ll test,cnt,ccnt,tot,num,sccCnt,x,y,vx,vy;
ll last[MAXN<<1],dfn[MAXN<<1],low[MAXN<<1],belong[MAXN<<1],ins[MAXN<<1];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline ll getType()
{
    register char ch=getchar();
    while(ch!='m'&&ch!='h')
    {
        ch=getchar();
    }
    return ch=='h';
}
inline void addEdge(ll from,ll to)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    last[from]=tot;
}
inline void addOr(ll x,ll y,ll vx,ll vy)
{
    addEdge(y+cnt*(vy^1),x+cnt*(vx&1));
    addEdge(x+cnt*(vx^1),y+cnt*(vy&1));
}
inline void Tarjan(ll node)
{
    ll nd;
    dfn[node]=low[node]=++num;
    st.push(node),ins[node]=1;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(!dfn[ed[i].to])
        {
            Tarjan(ed[i].to);
            low[node]=min(low[node],low[ed[i].to]);
        }
        else
        {
            if(ins[ed[i].to])
            {
                low[node]=min(low[node],dfn[ed[i].to]);
            }
        }
    }
    if(dfn[node]==low[node])
    {
        sccCnt++;
        do
        {
            nd=st.top(),st.pop();
            ins[nd]=0,belong[nd]=sccCnt;
        }
        while(node!=nd);
    }
}
inline void solve()
{
    cnt=read(),ccnt=read();
    for(register int i=0;i<ccnt;i++)
    {
        vx=getType(),x=read(),vy=getType(),y=read();
        addOr(x,y,vx,vy);
    }
    for(register int i=1;i<=(cnt<<1);i++)
    {
        if(!dfn[i])
        {
            Tarjan(i);
        }
    }
    for(register int i=1;i<=cnt;i++)
    {
        if(belong[i]==belong[i+cnt])
        {
            puts("BAD");
            return;
        }
    }
    puts("GOOD");
}
inline void clear()
{
    memset(ed,0,sizeof(ed)),memset(last,0,sizeof(last));
    memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)); 
    memset(belong,0,sizeof(belong)),memset(ins,0,sizeof(ins)); 
    tot=num=sccCnt=0;
    while(!st.empty())
    {
        st.pop();
    }
}
int main()
{
    test=read();
    for(register int i=0;i<test;i++)
    {
        solve(),clear();
    }
}