CF228E The Road to Berland is Paved With Good Intentions(2-sat)

CF228E The Road to Berland is Paved With Good Intentions

题意:

给定一个图(点数<=100),每条边的权值为0或1,每次可以对一个点进行操作,操作会改变这个点所有的边的权值(0变为1,1变为0)。求一种方案数,使得所有边都为1。

思路:

2-sat问题,不是很好想。

1.首先我们可以知道,如果一个边的权值改变的次数>=1后,影响和改变0/1次是一样的,所以过多的改变次数不考虑。所以改变次数只有0/1两种选择,就转化成了2-sat问题。

2.当前边为:u,v,w

如果w为0的话,那么u和v的操作次数为:u 0 次 v 1 次或 u 1 次 v 0 次。

如果w为0的话,u和v的操作次数为: u 0 次 v 0 次或 u 1 次 v 1 次。

3.考虑建图:

假设u表示操作次数为0次,u+n表示操作次数为1次。

分别对上述情况建图。要注意的点就是要建立双向边,因为条件是且。

4.判断是否有解:

按照一般的思路,如果矛盾点在同一个强连通分量里,说明相矛盾,问题无解。

5.输出方案:

要注意的是在这一步里矛盾点一定不在同一个连通分量里。

所以只需要对所有0-1边或1-0边进行输出即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;

vector<int>g[maxn];
int n,m;

void add(int u,int v){
	g[u].push_back(v);
	g[v].push_back(u);
}

int dfn[maxn],low[maxn],timetmp,id[maxn],cnt;
bool instk[maxn];
stack<int>stk;

void tarjan(int u){
	dfn[u]=low[u]=++timetmp;
	stk.push(u);
	instk[u]=1;
	for(int t:g[u]){
		if(!dfn[t]){
			tarjan(t);
			low[u]=min(low[u],low[t]);
		}
		else if(instk[t]) low[u]=min(low[u],dfn[t]);
	}
	if(low[u]==dfn[u]){
		int y;cnt++;
		do{
			y=stk.top();
			stk.pop();
			instk[y]=0;
			id[y]=cnt;
		}while(y!=u);
	}
}

int res[maxn],idx;

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		if(w==0){
			add(u+n,v);add(u,v+n);
		}
		else{
			add(u,v);add(u+n,v+n);
		}
	}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
		if(id[i]==id[i+n]){
			puts("Impossible");return 0;
		}
	for(int i=1;i<=n;i++)
		if(id[i]<id[i+n]){
			res[++idx]=i;
		}
	cout<<idx<<endl;
	for(int i=1;i<=idx;i++)
		cout<<res[i]<<" ";
	
	
	
	     
	
	
	
	
	
	
		
	return 0;
}
上一篇:Unity之AssetBundles基础


下一篇:Educational Codeforces Round 93 (Rated for Div. 2) C. Good Subarrays(前缀和优化技巧)