题目描述

有n个变量，m条语句，没个形如：xi为a或xj为b(a,b=0或1)...

判断是否有解，有的话构造出来一组解

 

 

思路:

• 将每个变量分为两个点，取0和取1(i和i+n)
• 对于每条语句可以转换为若xi取(1-a)则xj必须取b，若xj取(1-b)则xi必须取a,按照这样的关系连边
• 跑一遍tarjan，则在同一个强连通分量中如果取了一个点，那么一定要取其中的其他的点，如果i与i+n在同一个强连通分量，则一定无解
• 有解时，先缩点，然后每次找到出度为0的点，选取它，并删除即可，这样得到的操作序列就相当于倒着跑一遍拓扑排序(因为拓扑排序是先找入度为0的点)
• 又注意到tarjan后的col数组其实就是一个自底向上的拓扑序,所以我们每次选出度最小的点就相当于选col小的点

代码:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define res register intinline int read(){ int x=0,f=1; char ch; while(!isdigit(ch=getchar())) if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}const int N=4e6+5,M=4e6+5;int head[N],fron[M],ver[M],nxt[M];int tot,n,m;inline void add(int x,int y){ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}int dfn[N],low[N],col[N],colnum,num;bool ins[N];stack 
           
             s;void tarjian(int x){ dfn[x]=low[x]=++num; s.push(x); ins[x]=1; for(res i=head[x],y ; i ; i=nxt[i]) if(!dfn[y=ver[i]]) tarjian(y),low[x]=min(low[x],low[y]); else if(ins[y]) low[x]=min(low[x],dfn[y]); if(dfn[x]==low[x]) { ++colnum; int y; do { y=s.top(); s.pop(); ins[y]=0; col[y]=colnum; }while(x!=y); }}// xi=xj-> yi=yjint opp[N];inline void work(){ for(res i=1 ; i<=n*2 ; ++i) if(!dfn[i]) tarjian(i); for(res i=1 ; i<=n ; ++i) { if(col[i]==col[n+i]) { puts("IMPOSSIBLE"); return; } } puts("POSSIBLE"); for(res i=1 ; i<=n ; ++i) printf("%d ", col[i] > col[i+n]);//col[i]
            
             取0}int main(){ n=read(); m=read(); for(res i=1 ; i<=m ; ++i) { int a=read(),b=read(),c=read(),d=read(); // a=b^1 -> c=d // c=d^1 -> a=b add(a+(b^1)*n,c+d*n); add(c+(d^1)*n,a+b*n); } work(); return 0;}