首页 > 其他分享 >2-sat 模板

2-sat 模板

时间:2024-08-16 20:38:31浏览次数:15  
标签:const int scc define low include 模板 sat

2-Sat

\[\begin{align*} &\LARGE\color{Red}大意:\\ &有n个数a_i,m个约束条件都需要满足\\ &条件形如(i,a,j,b) \quad a_i=a \ \text{or} \ a_j=b\\\\\\ &\LARGE\color{Red}思路:\\ &让a_i表示0,a_{i+n}表示1\\ &转换条件表达式成:\\ &a_i =a \ \ \text{or} \ a_j=b \\ &case1:a_i=a,a_j\not=b\\ &case2:a_j=b,a_i\not=a\\ &case1:\ 连接(i+a*n,j+!b*n)\\ &case2:\ 连接(j+b*n,a+!a*n)\\ &然后跑Tarjan判断就好 \end{align*} \]

如果i和i+n在一个scc里面肯定不行 因为a_i只能为1或者0,不能同时为1或0


/**/
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define ep emplace_back 

#define int long long 
#define lld long long 
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0); 
#define vec vector 
const int N = 2e6+9;
const int INF = 0x7FFFFFFF; //2147483647

const int inf1 = 0x3f3f3f3f; //1061109567
const int inf2 = 0x7f7f7f7f; //2139062143 memset赋值用

using namespace std;
int head[N],idx=0;
struct node{
    int to,val,next;
}e[N<<1];
int scc[N],scc_cnt;
int n,m;
bool vis[N];
int low[N],dfn[N];
void add(int u,int v,int val){
    e[idx] = {v,val,head[u]};
    head[u] = idx++;
}
int time__=0;
stack<int>st;
void tarjan(int u){
    dfn[u] = low[u] = ++time__;
    vis[u] = 1;
    st.push(u);
    for(int i=head[u] ; i!=-1 ; i=e[i].next){
        int v = e[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(low[u] ==dfn[u]){
        ++scc_cnt;
        while(1){
            int v = st.top();
            st.pop();
            vis[v] = false;
            scc[v] = scc_cnt;
            if(v==u) break;
        }
    }
}
void bd(){
    cin>>n>>m;
    memset(head,-1,sizeof head);
    for(int k=1 ; k<=m ; ++k){
        int i,a,j,b;
        cin>>i>>a>>j>>b;
        //a_i:0
        //a_i:1
        add(i + a * n, j + !b * n, 0);       
        add(j + b * n, i + !a * n, 0);
    }
}
signed main(){
    ios;

    bd();
    for(int i=1 ; i<=2*n ; ++i)
        if(!dfn[i])
            tarjan(i);
    bool ok =1;//是否有解
    for(int i=1 ; i<=n ; ++i){
        if(scc[i] == scc[i+n]){
            ok=0;
            break;
        }
    }
    //如果 i和i+n在同一个scc里面 就无解 
    //否则输出方案
    if(ok){
        cout<<"POSSIBLE"<<"\n";
        for(int i=1 ; i<=n;++i){
           cout << (scc[i] > scc[i + n] ? 0 : 1) << " ";
        }
    }
    else {
        cout<<"IMPOSSIBLE";
    }
    return 0;
}

标签:const,int,scc,define,low,include,模板,sat
From: https://www.cnblogs.com/Phrink734/p/18363601

相关文章

  • 【CPP】C++模板:初阶到进阶语法与实用编程示例
    关于我:睡觉待开机:个人主页个人专栏:《优选算法》《C语言》《CPP》生活的理想,就是为了理想的生活!作者留言PDF版免费提供:倘若有需要,想拿我写的博客进行学习和交流,可以私信我将免费提供PDF版。留下你的建议:倘若你发现本文中的内容和配图有任何错误或改进建......
  • C# WPF现代化开发:绑定、模板与动画进阶
    ......
  • Proxmox VE换系统源和CT模板源
    debian换源#debian换源sed-i.bak"s#ftp.debian.org/debian#mirrors.aliyun.com/debian#g"/etc/apt/sources.listsed-i"s#security.debian.org#mirrors.aliyun.com/debian-security#g"/etc/apt/sources.listPVE换源#PVE换源echo"#debhttps:/......
  • 算法模板
    拓扑排序点击查看代码publicBooleanbfsOptimize(intn,int[][]edges){//初始化入度数组,每个节点有两个元素,第一个元素表示入度,第二个元素暂时未使用int[][]indegrees=newint[n][2];//初始化邻接表,用于存储图的连接关系List<List<Integer>>adj......
  • 61. 类模板(上)
    类是C++的核心,那是否能够将模板的思想应用于类呢?类模板一些类主要用于存储和组织数据元素,如:数组类,链表类,Stack类,Queue类等C++中可以将模板的思想应用于类,使得类的可以不关注具体所操作的数据类型,而只关注类所需要实现的功能。 C++中的类模板提供一种特殊的类以相同的行......
  • 62. 类模板(下)
    类模板的局部特化类模板可以定义多个类型参数#include<cstdlib>#include<iostream>usingnamespacestd;template<typenameT1,typenameT2>classTest{public:  voidadd(T1a,T2b)  {    cout<<(a+b)<<endl;  }};intmain(inta......
  • x264 编码器像素运算系列:satd 函数
    x264编码器中像素运算在x264编码器中有多种像素间的运算,如下:sad计算:SAD(SumofAbsoluteDifferences,绝对差值和)是一种在图像处理和视频编码中常用的度量,用于计算两个图像块之间的差异。SAD值越小,表示两个图像块越相似。hadamard_ac计算:用于计算Hadamard变换后非零......
  • 广度优先算法 BFS总结(算法详解+模板+例题)
    一.bfs是什么广度优先搜索(Breadth-FirstSearch,简称BFS),是一种图遍历算法。它从给定的起始节点开始,逐层地向外扩展,先访问起始节点的相邻节点,然后再访问相邻节点的相邻节点,以此类推,直到遍历完所有可达节点。二.基本思路1.一直往前走,直到到达终点。2.遇到分岔路口直接分出几条......
  • 小猫爬山——dfs模板题一道
    最近做搜索里面的题目,发现还是有很多漏洞的比如下面这道小猫爬山题,还是不会做看的答案...气死我了小猫爬山时间限制: 1.000 Sec  内存限制: 128MB提交 状态题目描述Freda和rainbow饲养了N只小猫,这天,小猫们要去爬山。经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦......
  • D44 2-SAT+前缀优化+二分 CF587D Duff in Mafia
    视频链接: CF587DDuffinMafia-洛谷|计算机科学教育新生态(luogu.com.cn)#include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;constintN=500005;inthead[N],idx,ne[N*6],to[N*6];voidadd(intx,......