P4171 [JSOI2010]满汉全席 题解

CSDN同步

原题链接

前置知识:\(\text{2 - SAT}\) 模板

简要题意:

烹饪比赛中你需要用 \(n\) 种材料,每种材料有两种烧法。(所谓汉式料理和满式)然后,\(m\) 个评委,每个评委都有要求:对第 \(x\) 道菜用第 \(p\) 种烧法(\(p \in {1,2}\)),或者 对第 \(y\) 道菜用第 \(q\) 种烧法(\(q \in {1,2}\)). 是否有一种方案能让所有评委满足要求?(不必输出方案)

显然本题和 \(\text{2-SAT}\) 类似,即建立布尔方程用模板解决。

关键,如何建立方程?即,如何建图?

首先,\((x,p,y,q)\) 应该要转化为:\(x_i = p\) 或 \(x_j = q\) 这种形式。

考虑一下,这是本来的建图的代码:

int a=read(),va=read(),b=read(),vb=read();
		G[a+n*(va&1)].push_back(b+n*(vb^1));
		G[b+n*(vb&1)].push_back(a+n*(va^1));

我们不想改动 \(\text{vector}\) 的函数那两行,只想预处理出 \(a,va,b,vb\) 的值。

显然,\(a\) 和 \(b\) 应当分别对应 \(p\) 和 \(q\),\(va\) 和 \(vb\) 分别对应 \(x\) 和 \(y\),这样子建图就可以保证万无一失啦!

  • 读入字符可以用 \(\text{scanf}\),但快读较好。

  • 注意 \(\text{vector}\) 的清空操作,不是 for(int i=1;i<=n;i++),而是 for(int i=1;i<=(n<<1);i++),时刻注意我们是 \(n \times 2\) 的图!

时间复杂度:\(O(T \times (n+m))\).(这题数据弱,导致 \(T \times nm\) 的暴力也过了,丧尽天良!)

实际得分:\(100pts\).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=2e3+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

bool h[N]; int cnt=0;
int times,dfn[N];
int low[N],n,m,f[N];
vector<int>G[N];
stack<int>s;

inline void dfs(int u) {
	dfn[u]=low[u]=++times;
	s.push(u); h[u]=1;
	for(int i=0,t;i<G[u].size();i++) {
		t=G[u][i];
		if(!dfn[t]) {
			dfs(t); low[u]=min(low[u],low[t]);
		} else if(h[t]) low[u]=min(low[u],dfn[t]);
	}
	if(low[u]==dfn[u]) {
		cnt++; int k;
		do {
//			a[cnt].push_back(s.top());
			k=s.top();
			h[k]=0; f[k]=cnt;
			s.pop();
		} while(k!=u) ;
	}
}

template<typename T>inline void _read_(T &EE,T &X){
	EE=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) X=c=='m'?1:X,X=c=='h'?0:X;
	for(;isdigit(c);c=getchar()) EE=(EE<<1)+(EE<<3)+(c^48);
}

int main(){
	int T=read(); while(T--) {
		int n=read(),m=read(); while(m--) {
			int a,a1,b,b1;
			_read_(a,a1); _read_(b,b1); //建图
			G[a+(a1^1)*n].push_back(b+b1*n);
			G[b+(b1^1)*n].push_back(a+a1*n); 
		} for(int i=1;i<=(n<<1);i++)
			if(!dfn[i]) dfs(i);
		for(int i=1;i<=n;i++)
			if(f[i]==f[i+n]) {
				puts("BAD");
				goto fin;
			} puts("GOOD"); goto fin;
		fin: { //记得数据还原
			memset(f,0,sizeof(f));
			memset(low,0,sizeof(low));
			memset(dfn,0,sizeof(dfn));
			for(int i=1;i<=(n<<1);i++) G[i].erase(G[i].begin(),G[i].end());
		}
	}
	return 0;
}

上一篇:Mac环境下JDK安装方法


下一篇:codeforces757F Team Rocket Rises Again【支配树+倍增+拓扑+spfa】