[BalticOI 2008] 阀门

思路

为什么评紫？2-SAT 模板直接搬过来都能 A。

设每个开关的状态为 $x_i$，观察到对于每个限制都要满足「$x_i$ 为 true / false 或 $x_j$ 为 true / false」，因为对于每条水管至少要有一个阀门关闭才能保证水管关闭。

显然该问题满足 2-SAT 的形式，具体可见【模板】2-SAT，直接套用模板即可。

注意本题内存限制比较小，对于某些写法可能需要优化空间复杂度。

代码

#include <bits/stdc++.h>
#define to(x) (x<=n?x+n:x-n)
using namespace std;
struct node{
	int x;
	bool y;
};
int n,m,col[1000005],nc;
vector<node> t[1000005];
vector<int> id;
bitset<1000005> vis;
void add(int x,int y){
	t[x].push_back({y,0});
	t[y].push_back({x,1});
}
void dfs(int x){
	vis[x]=true;
	for(node &v:t[x])
		if(!v.y&&!vis[v.x]) dfs(v.x);
	id.push_back(x);
}
void dfs2(int x){
	col[x]=nc;
	for(node v:t[x])
		if(v.y&&!col[v.x]) dfs2(v.x);
}
void kosaraju(){
	for(int i=1;i<=n;i++)
		if(!vis[i]) dfs(i);
	for(int i=id.size()-1;i>=0;i--){
		if(col[id[i]]) continue;
		nc++,dfs2(id[i]);
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>m>>n;
	for(int x,xx,y,yy,i=1;i<=m;i++){
		cin>>x>>xx>>y>>yy;
		if(xx) x+=n;
		if(yy) y+=n;
		add(to(y),x);
		add(to(x),y);
	}
	n*=2;
	kosaraju();
	for(int i=1;i<=n/2;i++){
		if(col[i]==col[i+n/2]){
			cout<<"IMPOSSIBLE";
			return 0;
		}
	}
	for(int i=1;i<=n/2;i++){
		if(col[i]>col[i+n/2])
			cout<<0<<endl;
		else
			cout<<1<<endl;
	}
	return 0;
}

记录