本文共 2643 字，大约阅读时间需要 8 分钟。

问题

$n$个布尔变量,$m$组限制,每组限制形如$a,x,b,y$

表示$a=x$和$b=y$一定有一个成立(其中$x,y$是布尔值)

求出一组可行解,或者说明这是不可能的

拆点,原图中的点$i$表示$false$,$i+n$表示$true$

对于$a=true||b==false$一定成立其中的至少一个

如果$a$的值为$false$那么$b$一定是$false$

对应的,我们连边$a->b$

如果$b$的值为$true$那么$a$一定是$true$

对应的,我们连边$b+n->a+n$

这样有什么好处…看个图

若$x_1$是$true$, 可以推断$x_1$是$false$,所以矛盾,即$x_1$不是$true$

若$x_1$是$false$, 可以推断$x_1$是$true$,所以矛盾,即$x_1$不是$false$

所以$x_1$啥也不是,无解。

所以判断有没有解,只需要看一下同一个点的两个状态是否在同一个强连通中即可

在这副图中,如何构造解??

显然如果取$x_1=false$可以推断$x_1=true$,所以我们应该选择$x_1=true$

也就是两个状态中,被指向的那个状态

其实就是$DAG$中的拓扑序,而$tarjan$算法的$scc$是由栈形成的

一定是经过了前驱的强连通分量到达被指向的强连通分量,然后弹栈

所以$scc$编号越小的,是被指向的强连通,我们应该选择

#include 
   
    using namespace std;const int maxn = 4e6+10;struct edge{
   int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
       d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt;}int n,m;int low[maxn],dfn[maxn],scc[maxn],vis[maxn],stac[maxn],sc,id,top;void tarjan(int u){
       dfn[u] = low[u] = ++id; stac[++top] = u; vis[u] = 1;    for(int i=head[u];i;i=d[i].nxt )    {
           int v = d[i].to;        if( !dfn[v] )   tarjan(v),low[u] = min( low[u],low[v] );        else if( vis[v] )   low[u] = min( low[u],dfn[v] );    }    if( dfn[u] == low[u] )    {
           int temp; ++sc;        while( temp=stac[top--] )        {
               vis[temp] = 0, scc[temp] = sc;            if( temp==u )   break;        }    }}int main(){
       cin >> n >> m;    for(int i=1;i<=m;i++)    {
           int a,x,b,y; scanf("%d%d%d%d",&a,&x,&b,&y);        if( x==0 && y ==0 )            add( a+n,b),add(b+n,a);//一方为真,另一方一定是假        else if( x==0&&y==1 )            add( a+n,b+n ),add( b,a );        else if( x==1&&y==0 )            add( a,b ),add( b+n,a+n );        else if( x==1 && y==1 )            add( a,b+n ),add( b,a+n );    }    for(int i=1;i<=n+n;i++)        if( !dfn[i] )   tarjan(i);    for(int i=1;i<=n;i++)        if( scc[i]==scc[i+n] )        {
               printf("IMPOSSIBLE\n");            return 0;        }    puts("POSSIBLE");    for(int i=1;i<=n;i++)    {
           if( scc[i]>scc[i+n] )   printf("1 ");        else    printf("0 ");    }    return 0;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115384396 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！