[JSOI2010] 满汉全席
Problem
一种材料可以做成满式和汉式。
每个厨师想吃两道菜,可能是某个材料做成的某道菜式。
只要满足厨师的一道菜就可以得到厨师的认可。
问是否有一种方案来做材料来得到所有厨师的认可。
Solution
接近 2 -SAT 的裸题。
设第 i 种材料为 $A_i$,$A_i$ 等于 0 代表满式,等于 1 则反之。
所以如果厨师想吃 i 菜的满,j 菜的汉,则约束条件为:
!A[i]||A[j]
以此类推,汉汉:
A[i]||A[j]
满满:
!A[i]||!A[j]
用 2 -SAT 直接判断是否有可行解就 OK 了。
// Code by ajcxsu
// Problem: Food
#include<bits/stdc++.h>
#define CLR(x) memset(x,0,sizeof(x))
#define ASS(x) ((x)+100)
using namespace std;
int n,m;
const int N=210, M=1e5+10;
int h[N],to[M],nexp[M],p=1;
int dfn[N], low[N], idx;
int scc[N], sidx;
int stk[N], top;
bool instk[N];
inline void init() { CLR(h), p=1; CLR(dfn), CLR(low), idx=0; CLR(scc), sidx=0; }
inline void ins(int a,int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
void tarjan(int x) {
dfn[x]=low[x]=++idx;
instk[x]=1;
stk[top++]=x;
for(int u=h[x];u;u=nexp[u])
if(!dfn[to[u]]) {
tarjan(to[u]);
low[x]=min(low[x], low[to[u]]);
}
else if(instk[to[u]]) low[x]=min(low[x], dfn[to[u]]);
if(low[x]==dfn[x]) {
sidx++;
do {
top--;
scc[stk[top]]=sidx;
instk[stk[top]]=0;
} while(stk[top]!=x);
}
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n>>m;
init();
char ch1,ch2;
int val1,val2;
for(int i=0;i<m;i++) {
cin>>ch1>>val1>>ch2>>val2;
if(ch1!=ch2) {
if(ch1=='h') swap(val1, val2);
ins(val1,val2), ins(ASS(val2), ASS(val1));
}
else {
if(ch1=='m') ins(val1, ASS(val2)), ins(val2, ASS(val1));
else ins(ASS(val1), val2), ins(ASS(val2), val1);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
bool ans=1;
for(int i=1;i<=n && ans;i++) if(scc[i]==scc[ASS(i)]) ans=0;
if(!ans) cout<<"BAD"<<endl;
else cout<<"GOOD"<<endl;
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol_luogu_4171.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆