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;
}