首页 > 其他分享 >常见优化建图技巧

常见优化建图技巧

时间:2023-09-02 10:34:20浏览次数:48  
标签:连边 技巧 int namespace flag add 建图 优化 id

一、线段树优化建图

基本操作

  1. \(x\) 向区间 \([l,r]\) 连边
  2. 区间 \([l,r]\) 向 \(x\) 连边
  3. 区间 \([l,r]\) 向 区间 \([x,y]\) 连边

建立两棵线段树,一棵从父亲节点向儿子节点连长度为 \(0\) 的边,称为出树;一棵从儿子节点向父亲连长度为 \(0\) 的边,称为入树。并且在出树和入树的相同叶子节点间连长度为 \(0\) 的边

对于操作1,在入树中找到 \(x\) 代表的点,向出树中 \([l,r]\) 覆盖的点连边

对于操作2,在入树中找到 \([l,r]\) 覆盖的点,向出树中 \(x\) 代表的的点连边

对于操作3,在入树中找到 \([l,r]\) 覆盖的点,向虚点连边,虚点再向出树中 \([x,y]\) 覆盖的点连边

这样,我们将边数规模从 \(O(n^2m)\) 降到了 \(O(m\log n)\),方便我们进行后续操作

CF786B Legacy

板子题

code
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pli pair<long long,int>
#define LL long long
using namespace std;

const int N=100010;

int n,m,s;
vector <pii> g[9*N];

void add(int x,int y,int z)
{
	g[x].push_back({y,z});
}

namespace TR
{
	#define lc(p) p*2
	#define rc(p) p*2+1
	int cnt;
	
	struct SegmentTree
	{
		int id[4*N],pos[N];
		
		void build(int p,int l,int r,int flag)
		{
			id[p]=++cnt;
			if(l==r)
			{
				pos[l]=cnt;
				return;
			}
			int mid=(l+r)>>1;
			build(lc(p),l,mid,flag);  build(rc(p),mid+1,r,flag);
			if(!flag)
				add(id[p],id[lc(p)],0),add(id[p],id[rc(p)],0);
			else
				add(id[lc(p)],id[p],0),add(id[rc(p)],id[p],0);
		}
		
		void addt(int p,int l,int r,int ql,int qr,int u,int w,int flag)
		{
			if(ql<=l && qr>=r)
			{
				if(!flag)
					add(u,id[p],w);
				else
					add(id[p],u,w);
				return;
			}
			int mid=(l+r)>>1;
			if(ql<=mid)
				addt(lc(p),l,mid,ql,qr,u,w,flag);
			if(qr>mid)
				addt(rc(p),mid+1,r,ql,qr,u,w,flag);
		}
	}t[2];
}

namespace GR
{
	LL d[9*N];  bool v[9*N];
	priority_queue <pli> q;
	
	void dijkstra()
	{
		memset(d,0x3f,sizeof(d));
		d[TR::t[1].pos[s]]=0;  q.push({0,TR::t[1].pos[s]}); 
		while(q.size())
		{
			int x=q.top().second;  q.pop();
			if(v[x])
				continue;
			v[x]=1;
			for(auto vv:g[x])
			{
				int y=vv.first,z=vv.second;
				if(d[y]>d[x]+(LL)z)
					d[y]=d[x]+(LL)z,q.push({-d[y],y});
			}
		}
	} 
}

int main()
{
	using namespace TR;
	using namespace GR;
	
	scanf("%d%d%d",&n,&m,&s);
	
	t[0].build(1,1,n,0);  t[1].build(1,1,n,1);
	for(int i=1; i<=n; i++)
		add(t[0].pos[i],t[1].pos[i],0),add(t[1].pos[i],t[0].pos[i],0);
		
	while(m--)
	{
		int op,u,v,w,l,r;
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d",&u,&v,&w);
			add(t[1].pos[u],t[0].pos[v],w);
		}
		else if(op==2)
		{
			scanf("%d%d%d%d",&u,&l,&r,&w);
			t[0].addt(1,1,n,l,r,t[1].pos[u],w,0);
		}
		else
		{
			scanf("%d%d%d%d",&u,&l,&r,&w);
			t[1].addt(1,1,n,l,r,t[0].pos[u],w,1);
		}
	}
	
	dijkstra();
	
	for(int i=1; i<=n; i++)
	{
		LL res=d[t[0].pos[i]];
		if(res>=1e18)
			printf("-1 ");
		else
			printf("%lld ",res);
	}

	return 0;
}

标签:连边,技巧,int,namespace,flag,add,建图,优化,id
From: https://www.cnblogs.com/xishanmeigao/p/17673288.html

相关文章

  • 前端学习笔记202308学习笔记第七十捌天-性能优化11
      ......
  • 前端学习笔记202308学习笔记第七十捌天-性能优化10
     ......
  • 前端学习笔记202308学习笔记第七十捌天-性能优化12
      ......
  • MAST90050调度与优化算法
    MAST90050-SchedulingandOptimisationAssignment1(25%)InstructionsTheassignmentmustbesubmittedonlineviatheMAST90050websitebefore11:59pmonThursday,August31.Latesubmissionsarenotacceptedunlessamedicalcertificateisprovided.Assig......
  • COMP3610编程技巧几点看法
    COMP3610/6361PrinciplesofProgrammingLanguagesAssignment1ver1.1SubmissionGuidelinesDuetime:Aug31,2023,11am(CanberraTime)SubmitapdfviaWattle.Scansofhand-writtentextarefine,aslongastheyarereadableandneat.Pleasereadandsign......
  • 优化函数迭代每次都要查找的代码
    在做Perfeye需求的时候,有写了一个函数,每次遍历,要根据相同的时间,把对应的数据整合刚开始用findIndex进行每次查找,但是性能很差,后面问了gpt有没有什么操作能不用findIndex,gpt说可以单独存储时间索引值来进行判断旧代码constgetFTimeDataSetSourceData=()=>{constresu......
  • 开发小技巧 - 合理使用Visual Studio 2022内置任务列表(TODO)
    前言在开发编码过程中经常会因为各种问题而打断自己的思绪和开发计划,可能会导致本来准备开发或者需要测试的功能到要上线的时候才想起来没有做完。这种情况相信很多同学都遇到过,咱们强大的VisualStudio内置了一个任务列表(TODO)能让我们当做待办清单功能使用,接下来我们快速了解一......
  • nginx优化相关
    https://blog.csdn.net/liuxiao723846/article/details/46862381Nginx反向代理,当后端为Https时的一些细节和原理_nginx反向代理https_赶路人儿的博客-CSDN博客 nginx-寒星12345678999-博客园(cnblogs.com)......
  • 从达梦数据库到Oracle数据库的性能测试数据迁移和导入优化
    为了在同样的数据基础上对比达梦数据库和Oracle数据库的业务性能,我们需要将达梦数据库的数据导入到Oracle数据库中。本文将提供一种思路来解决导入过程中遇到的问题及存在问题记录。数据库版本信息源数据库:达梦数据库(DM)V8目标数据库:Oracle数据库V11.2.0.4导出达梦数据库的......
  • 优化一个已有的 Go 程序,提高其性能并减少资源占用
    在软件开发中,性能和资源占用通常是我们关注的重点。优化一个已有的程序可以显著提高其性能,并减少对系统资源的占用。本文将介绍如何通过优化一个Go程序来实现这些目标。1.性能分析在开始优化之前,我们首先需要对程序进行性能分析,以确定瓶颈所在。在Go语言中,我们可以使用pprof工具......