首页 > 其他分享 >优化建图

优化建图

时间:2024-05-09 19:44:32浏览次数:21  
标签:囚犯 int 线段 建图 优化 define

写 \(2-SAT\) 时刷到的,发现好像一点不会,学习下。

1. 线段树优化建图

当一个点与一段区间连边时,暴力连是 \(O(n^2)\) 的。
因为线段树有一个肥肠优秀的性质,一个区间最多被分为 \(O(logn)\) 个节点。
so,我们可以把区间当成放到线段树上,这样是 \(O(nlogn)\) 的。
具体的,我们建立一个入线段树出线段树,初始都连长度为 \(0\) 的边。
这是图片
建图时根据区间建即可。

  • 当区间到区间建图时,可以建立一个 虚点,让 区间->虚点p->区间,复杂度不变,常数较大。

肥肠的神奇啊。

I CF786B Legacy

裸题,建树建边即可,详见代码

#include <bits/stdc++.h> 
using namespace std;
//线段树优化建图模版 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define inf 1e18
//神tm pair要开longlong!!! 

const int N = 2e6+10,K = 5e5;


int n,q,s;
struct made{
    int ver,nx;ll ed;
}e[N<<1];
int hd[N],tot;
void add(int x,int y,ll z){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}


int a[N];
void build(int p,int l,int r){
    if(l == r)return a[l] = p,void();
    add(p<<1,p,0),add(p<<1|1,p,0);
    add(p+K,(p<<1)+K,0),add(p+K,(p<<1|1)+K,0);
    int mid = l + r >> 1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void add(int p,int x,int L,int R,int l,int r,ll z,bool op){
    if(L <= l && r <= R)return op?add(a[x],p+K,z) : add(p,a[x]+K,z),void();
    int mid = l + r >> 1;
    if(L <= mid)add(p<<1,x,L,R,l,mid,z,op);//
    if(R > mid)add(p<<1|1,x,L,R,mid+1,r,z,op);
}//线段树建 入树(p) 与 出树(p+K)


bool v[N];
ll d[N];
void dij(int u){
    memset(v,0,sizeof v);
    for(int i = 1;i <= 2*K;i++)d[i] = inf;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    d[u] = 0;q.push(mp(0,u));
    while(!q.empty()){
        int x = q.top().se;q.pop();
        if(v[x])continue;
        v[x] = 1;
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver;ll z = e[i].ed;
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push(mp(d[y],y));
            }
        }
    }
}//dijdij
int main(){
    scanf("%d%d%d",&n,&q,&s);
    build(1,1,n);
    for(int i = 1;i <= n;i++)add(a[i]+K,a[i],0);
    for(int i = 1;i <= q;i++){
        int op,x,y,l,r;ll z;
        scanf("%d%d",&op,&x);
        if(op == 1)scanf("%d%lld",&y,&z),add(a[x],a[y]+K,z);
        else if(op == 2)scanf("%d%d%lld",&l,&r,&z),add(1,x,l,r,1,n,z,1);
        else scanf("%d%d%lld",&l,&r,&z),add(1,x,l,r,1,n,z,0);
    }
    dij(a[s]);
    for(int i = 1;i <= n;i++){
        if(d[a[i]] == inf)printf("-1 ");
        else printf("%lld ",d[a[i]]);
    }
    printf("\n");
    
    
    
    return 0;
    
}

II P6348 [PA2011] Journeys
裸题,只是区间向区间连边

代码

III P9520 [JOISC2022] 监狱
非常好的一道题。

我们可以发现一个性质

  • 如果一个方案满足条件,则必然存在一种情况使每个囚犯都独立的由起点走向终点。
  • 证明:如果一个囚犯走到一半,另一个囚犯再走这种方案满足条件,则两个囚犯独立走也一定满足条件。

所以每个囚犯只需自己走即可。
我们考虑囚犯的先后顺序,定义有向边 \((x,y)\) 代表 \(x\) 号囚犯需要第 \(y\) 号囚犯先走,才可以满足条件。
可以发现:

  • 一个囚犯 \(i\),若有囚犯 \(j\) 的起点在囚犯 \(i\) 的路径上时,需要连接 \(i \rightarrow j\)
  • 类似的,一个囚犯 \(i\),若有囚犯 \(j\) 的终点在囚犯 \(i\) 的路径上时,需要连接 \(j \rightarrow i\)

最后只需判断是否存在即可。

但是这样的边数为 \(O(n^2)\),考虑优化建图。
因为我们判环可以 \(O(m)\) 判环,所以可以直接 树剖加线段树优化建图,直接 \(O(nlogn^2)\)。
能过。

不过在树上也可以用倍增优化建图前后缀优化建图
都可以把边数优化到 \(O(nlogn)\)。

  • 倍增优化的常数有些大,导致其实跑的差不多快

代码(树剖+线段树)

2. 前后缀优化建图

当我们需要一个集合内的点互相连边时,可优化到 \(O(n)\)。

I P6378 [PA2010] Riddle
可以发现,每条边至少选一个点,每个部分只能选一个点。

这是一个 \(2 - SAT\) 问题,只需要考虑 \(!p \rightarrow q\) 和 \(p \rightarrow !q\) 即可。
但这样我们发现边数是 \(O(n^2)\) 的,用 \(tarjan\) 找环的复杂度也是 \(O(n^2)\) 的。

需要优化建图。
为了简化建边,我们需要一些多余的点,叫做虚点
我们可以首先把集合拉成一个序列,我们可以类似于前缀和一样建一个前缀节点,第 \(i\) 个前缀节点连着前 \(i\) 个点。
这样我们只需要多建 \(n\) 个点与 \(2n\) 条边就可完成建边。类似的,我们也同样建 \(n\) 个后缀节点
这样第 \(i\) 个点想要连接其他的点只需要连接第 \(i-1\) 个前缀节点与第 \(i+1\) 个后缀节点 两条边即可。

这样一共有 \(8n\) 条边,复杂度线性。
跑下 \(2-SAT\) 即可。

代码

II P5344 【XR-1】逛森林

标签:囚犯,int,线段,建图,优化,define
From: https://www.cnblogs.com/HaoXu-qwq/p/18172531

相关文章

  • 平时开发的优化代码:
    第一:检验,报错直接抛出异常: Objects.requireNonNull(contactId);第二:方法名,检查是否需要输出日志:if(printLogIfNeeded)//对于sql查询方法、java中的方法名字的命名定义推荐:find..By/query..By/get..By//检验查询结果是否业务需要返回的codeCustomerBuPOcustomerBu......
  • 优化cmd中,查询表字段过长情况下的展示效果
    当我们遇到table字段比较多,cmd无法在一行内展示所有字段的情况时可以切换查询语句的结束格式:由以分号;结尾select*fromtable;切换为以/G结尾select*fromtable/G可以切换table的展示格式为以竖列的形式展示一行一行的数据......
  • PVE安装后优化
    上传脚本文件至pve服务器,解压文件tarxvfpve_source.tar.gz解压出来有四个可执行脚本文件,脚本运行需要联网,保证外网通畅,执行./pve_source 1、去除订阅弹窗,输入6回车 2、web界面概要显示更多信息,输入7进入“修改PVE概要信息”,然后输入o使用推荐方案执行 ......
  • react 性能优化
    一纯组件1使用shouldComponentUpdate对先前的状态和props数据与下一个props或状态相同,如果两次的结果一直,那么就returnfalse使用纯净组件,pureComponentPureComponents负责shouldComponentUpdate——它对状态和props数据进行浅层比较(shallowcomparison),如果先前......
  • 关系代数与逻辑优化规则 (一): 定义
    作者:zhuwenzhuang,2024.05.08.阅读前假设读者熟悉数据库使用,了解SQL的语法和关系算子的大概含义,能通过EXPLAIN命令查看数据库执行计划.0前言数据库优化器的查询优化(QueryOptimization)指在查询等价的前提下,将代价更高的查询转化为代价更低的查询的过程.查询......
  • ES索引数据迁移、分片数优化(reindex)
    目录ES索引数据迁移、分片数优化(reindex)业务背景步骤新建索引将原索引数据复制到新索引中校验结果删除原索引给新索引起别名创建新索引的metric脚本整合使用感受ES索引数据迁移、分片数优化(reindex)​ Elasticsearch是⼀个实时的分布式搜索引擎,为⽤户提供搜索服务。当我们创建好......
  • 日常系统批处理优化案例(来源网络)
    @ECHOoffECHO关闭WindowsDefenderregadd"HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\WindowsDefender"/v"DisableAntiSpyware"/d1/tREG_DWORD/fecho完成ECHO关闭Windows防火墙regadd"HKEY_LOCAL_MACHINE\SOFTWARE\Polici......
  • 在Linux中,如何进行系统性能优化?
    在Linux系统中进行性能优化是一个综合性的过程,涉及多个层面,包括但不限于CPU、内存、磁盘I/O、网络以及应用程序本身的优化。以下是一些基本步骤和策略:1.识别性能瓶颈监控工具:首先使用诸如top、htop、vmstat、iostat、netstat、sar等工具来监视系统的实时状态,识别出CPU、内存、......
  • mysql死锁优化
    查看连接showprocesslist--已开启10秒以上的活跃连接SELECTid,user,db,command,state,time,infoFROMinformation_schema.processlistwherecommand<>'sleep'andtime>10orderbytime;--已运行超过10s的执行计划SELECTid,user,db,command,state,timeFROMinfo......
  • ITIL4 视角下的请求管理:优化服务体验的现代实践
    在当今复杂的IT服务管理环境中,请求管理作为ITIL4框架中的一个重要实践,扮演着连接用户需求与高效服务交付的桥梁角色。请求管理主要处理那些非即时性、变更或事件驱动的用户需求,比如密码重置、软件安装、访问权限调整等。由于请求通常是工单系统中最频繁的服务类型,优化请求管理......