首页 > 其他分享 >最小瓶颈路

最小瓶颈路

时间：2024-03-07 13:26:36浏览次数：26  
标签：return 瓶颈 tr 最小 TP int ans using

Decribe:

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，编号为 \(1\) 到 \(n\) ，没有自环，可能有重边，每一条边有一个正权值 \(w\) 。
给出 \(q\) 个询问，每次给出两个不同的点 \(u\) 和 \(v\) ，求一条从 \(u\) 到 \(v\) 的路径上边权的最大值最小是多少。

\(n \leq 10^3, m \leq 10^5, q \leq 10^3\)

Solution:

普通版：

考虑 kruskal 的过程：每次选择最短的边，尝试加入当前的连通图。显然这样的过程是可以保证连通图的任何一个点到新加入的点的路径上边权的最大值最小。那就可以建一个最小生成树，再以这棵树套一个非常基础的树链剖分即可解决问题。但这不是我们重点介绍的内容，所以不过多赘述。时间复杂度 \(O(q \log^2 n)\)。

Code:
bool _Start;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
	#define TP template<typename T>
	#define TP_ template<typename T,typename ... T_>
	#ifdef DEBUG
	#define gc() (getchar())
	#else
	char buf[1<<20],*p1,*p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	#ifdef DEBUG
	void pc(const char &c)
	{
		putchar(c);
	}
	#else
	char pbuf[1<<20],*pp=pbuf;
	void pc(const char &c)
	{
		if(pp-pbuf==1<<20)
			fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
		*pp++=c;
	}
	struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
	#endif
	TP void read(T &x)
	{
		x=0;static int f;f=0;static char ch;ch=gc();
		for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
		for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
		f&&(x=-x);
	}
	TP void write(T x)
	{
		if(x<0)
			pc('-'),x=-x;
		static T sta[35],top;top=0;
		do
			sta[++top]=x%10,x/=10;
		while(x);
		while(top)
			pc(sta[top--]^48);
	}
	TP_ void read(T &x,T_&...y){read(x);read(y...);}
	TP void writeln(const T x){write(x);pc('\n');}
	TP void writesp(const T x){write(x);pc(' ');}
	TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
	TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
	TP void debug(const T x){fprintf(stderr,"%d\n",x);}
	TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
	TP inline T max(const T &a,const T &b){return a>b?a:b;}
	TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));} 
	TP inline T min(const T &a,const T &b){return a<b?a:b;}
	TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
	TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
	TP inline T abs(const T &a){return a>0?a:-a;}
	#undef TP
	#undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
constexpr int N=1e3+10,M=1e5+10,inf=1e9;
struct edge
{
	int y,c,pre;
}a[M<<1];int alen,last[N];
void ins(int x,int y,int c)
{
	a[++alen]=edge{y,c,last[x]};
	last[x]=alen;
}
int n,m;
namespace Rebuild
{
	int fa[N],siz[N];
	struct Edge
	{
		int x,y,c;
	}e[M];
	int findfa(int x)
	{
		return fa[x]==x?x:findfa(fa[x]);
	}
	bool merge(int x,int y)
	{
		int tx=findfa(x),ty=findfa(y);
		if(tx==ty)
			return false;
		if(siz[tx]>siz[ty])
		{
			fa[ty]=tx;
			siz[tx]+=siz[ty];
		}
		else
		{
			fa[tx]=ty;
			siz[ty]+=siz[tx];
		}
		return true;
	}
	void work()
	{
		for(int i=1;i<=n;i++)
			fa[i]=i,siz[i]=1;
		for(int i=1;i<=m;i++)
			read(e[i].x,e[i].y,e[i].c);
		std::sort(e+1,e+m+1,[](const Edge &x,const Edge &y){return x.c<y.c;});
		for(int i=1;i<=m;i++)
			if(merge(e[i].x,e[i].y))
			{
				ins(e[i].x,e[i].y,e[i].c);
				ins(e[i].y,e[i].x,e[i].c);
			}
	}
}
namespace Chain
{
	struct trnode
	{
		int fa,son,siz,dep,top,dfn,val;
	}tr[N];
	void prepare(int x,int fa)
	{
		tr[x]={fa,0,1,tr[fa].dep+1,0,0};
		for(int k=last[x];k;k=a[k].pre)
		{
			int y=a[k].y;
			if(y==fa)
				continue;
			prepare(y,x);
			tr[y].val=a[k].c;
			tr[x].siz+=tr[y].siz;
			if(tr[tr[x].son].siz<tr[y].siz)
				tr[x].son=y;
		}
	}
	int num,b[N];
	void dfs_chain(int x,int tp)
	{
		tr[x].top=tp;
		tr[x].dfn=++num;
		b[num]=x;
		if(tr[x].son)
			dfs_chain(tr[x].son,tp);
		for(int k=last[x];k;k=a[k].pre)
		{
			int y=a[k].y;
			if(y==tr[x].fa||y==tr[x].son)
				continue;
			dfs_chain(y,y);
		}
	}
}
namespace Segtree
{
	struct trnode
	{
		int l,r,lc,rc,c;
	}tr[N<<1];int trlen;
	#define lc tr[now].lc
	#define rc tr[now].rc
	void pushup(int now)
	{
		tr[now].c=max(tr[lc].c,tr[rc].c);
	}
	void build(int l,int r)
	{
		int now=++trlen;
		tr[now]={l,r};
		if(l==r)
			tr[now].c=Chain::tr[Chain::b[l]].val;
		else
		{
			int mid=(l+r)>>1;
			lc=trlen+1;build(l,mid);
			rc=trlen+1;build(mid+1,r);
			pushup(now);
		}
	}
	int query(int now,int l,int r)
	{
		if(l<=tr[now].l&&tr[now].r<=r)
			return tr[now].c;
		int ans=-inf,mid=(tr[now].l+tr[now].r)>>1;
		if(l<=mid)
			ans=max(ans,query(lc,l,r));
		if(r>=mid+1)
			ans=max(ans,query(rc,l,r));
		return ans;
	}
}
int query_route(int x,int y)
{
	using Rebuild::findfa;
	if(findfa(x)!=findfa(y))
		return -1;
	using namespace Chain;
	using Segtree::query;
	int ans=-inf;
	while(tr[x].top!=tr[y].top)
	{
		if(tr[tr[x].top].dep>tr[tr[y].top].dep)
			swap(x,y);
		ans=max(ans,query(1,tr[tr[y].top].dfn,tr[y].dfn));
		y=tr[tr[y].top].fa;
	}
	if(tr[x].dep>tr[y].dep)
		swap(x,y);
	ans=max(ans,query(1,tr[x].dfn+1,tr[y].dfn));
	return ans;
}
bool _End;
int main()
{
//	fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
	int q;read(n,m,q);
	Rebuild::work();
	for(int i=1;i<=n;i++)//loj 没说连通图
	if(!Chain::tr[i].top)
		{
			Chain::prepare(i,0);
			Chain::dfs_chain(i,i);
		}
	Segtree::build(1,Chain::num);
	while(q--)
	{
		int st,ed;
		read(st,ed);
		writeln(query_route(st,ed));
	}
	return 0;
}

加强版：

那如果是 $ n \leq 7 \times 10^4 ,k \leq 10^7$ 呢？显然上面的方法会 TLE。这时就要去西天请来另一种算法了————kruskal 重构树。

这个东东其实非常简单。在 kruskal 加入边的时候，稍稍改改：新建一个点，这个点的点权就是边权，再与边的两点建边，缩成一个集合。后面若是要与这个集合连边，就要与这个新建的点连边。

这个新的二叉树有一些有趣的性质：

  • 所有原来的点都在叶子上；

  • 原来树上的任意两点的路径最大边权就是这棵二叉树最近公共祖先的点权。

于是，只要在这棵树上求 LCA，就是题目所求。省去了树剖的链分配后求区间最小值，只需要单纯的求 LCA 即可，降了一只 log。

但再看看数据，\(O(k \log n)\) 仍然非常炸裂，只有常数极小的树剖求 LCA 才能勉强卡过去。（显然数据还不够强）我们还需要另一位神仙： \(O(1)\) LCA。

首先需要知道一个东西：欧拉序。它跟 dfs 序有点像，但又有所不同。欧拉序在每到达一个节点时，都要记录当前到达的节点编号，无论先前是否有记录。若是第一次到达，则对这个点编号为第几个到达的新点。

这对求 LCA 很有帮助。比如说取两个点，我只需要在欧拉序中找到这两个点编号之间最小的编号对应的点，就是两点的 LCA。因为如果要从一个点到达另一个点，显然一定要经过编号小的点（也就是回溯）再走向另一个点。所以我们只需要维护区间最小值即可。因为树是固定的，所以可以用 \(O(n \log n)\) 预处理、\(O(1)\) 静态查询的 ST 表即可。

最终时间复杂度 \(O(k)\)。

Code:
bool _Start;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
	#define TP template<typename T>
	#define TP_ template<typename T,typename ... T_>
	#ifdef DEBUG
	#define gc() (getchar())
	#else
	char buf[1<<20],*p1,*p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	#ifdef DEBUG
	void pc(const char &c)
	{
		putchar(c);
	}
	#else
	char pbuf[1<<20],*pp=pbuf;
	void pc(const char &c)
	{
		if(pp-pbuf==1<<20)
			fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
		*pp++=c;
	}
	struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
	#endif
	TP void read(T &x)
	{
		x=0;static int f;f=0;static char ch;ch=gc();
		for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
		for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
		f&&(x=-x);
	}
	TP void write(T x)
	{
		if(x<0)
			pc('-'),x=-x;
		static T sta[35],top;top=0;
		do
			sta[++top]=x%10,x/=10;
		while(x);
		while(top)
			pc(sta[top--]^48);
	}
	TP_ void read(T &x,T_&...y){read(x);read(y...);}
	TP void writeln(const T x){write(x);pc('\n');}
	TP void writesp(const T x){write(x);pc(' ');}
	TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
	TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
	TP void debug(const T x){fprintf(stderr,"%d\n",x);}
	TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
	TP inline T max(const T &a,const T &b){return a>b?a:b;}
	TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));} 
	TP inline T min(const T &a,const T &b){return a<b?a:b;}
	TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
	TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
	TP inline T abs(const T &a){return a>0?a:-a;}
	#undef TP
	#undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
constexpr int N=7e4+10,M=1e5+10,mod=1e9+7;
int n,m;
struct edge
{
	int y,pre;
}a[N<<2];int alen,last[N<<1];
inline void ins(int x,int y)
{
	a[++alen]=edge{y,last[x]};
	last[x]=alen;
}
int w[N<<1];
namespace Kruskal
{
	struct Edge
	{
		int x,y,c;
	}e[M];
	int fa[N<<1],num;
	int findfa(int x)
	{
		return fa[x]=fa[x]==x?x:findfa(fa[x]);
	}
	bool merge(int x,int y,int c)
	{
		int tx=findfa(x),ty=findfa(y);
		if(tx==ty)
			return false;
		++num;
		fa[tx]=num;
		fa[ty]=num;
		ins(tx,num),ins(num,tx);
		ins(ty,num),ins(num,ty);
		w[num]=c;
		return true;
	}
	void init()
	{
		for(int i=1;i<=n<<1;i++)
			fa[i]=i;
	}
	void build()
	{
		num=n;
		for(int i=1;i<=m;i++)
			read(e[i].x,e[i].y,e[i].c);
		std::sort(e+1,e+m+1,[](const Edge &x,const Edge &y){return x.c<y.c;});
		init();
		for(int i=1;i<=m;i++)
			merge(e[i].x,e[i].y,e[i].c);
	}
}
int pos[N<<1],ys[N<<2],tsp;
int f[N<<2][25],d[N<<2];
void dfs(int x,int fa)
{
	ys[pos[x]=++tsp]=x;
	f[tsp][0]=pos[x];
	for(int k=last[x];k;k=a[k].pre)
	{
		int y=a[k].y;
		if(y==fa)
			continue;
		dfs(y,x);
		f[++tsp][0]=pos[x];
	}
}
void prepare()
{
	for(int i=2;i<=tsp;i++)
		d[i]=d[i>>1]+1;
	for(int i=1;i<=tsp;i++)
		for(int j=1;1<<j<=i;j++)
			f[i][j]=min(f[i][j-1],f[i-(1<<(j-1))][j-1]);
}
int LCA(int x,int y)
{
	int l=pos[x],r=pos[y];
	if(l>r)
		swap(l,r);
	int k=d[r-l+1];
	return ys[min(f[l+(1<<k)-1][k],f[r][k])];
}
int A,B,C,P;
inline int rnd(){return A=(A*B+C)%P;}
bool _End;
int main()
{
//	fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
	read(n,m);
	Kruskal::build();
	dfs((n<<1)-1,0);
	prepare();
	int q;read(q,A,B,C,P);
	LL ans=0;
	while(q--)
	{
		int st=rnd()%n+1,ed=rnd()%n+1;
		ans+=w[LCA(st,ed)];
		if(ans>mod)
			ans-=mod;
	}
	writeln(ans);
	return 0;
}

标签：return,瓶颈,tr,最小,TP,int,ans,using
From： https://www.cnblogs.com/lofty2007/p/18056381

相关文章

  • 代码随想录算法训练营第二天| 977.有序数组的平方、 209.长度最小的子数组、 59.螺旋
    977.有序数组的平方https://leetcode.cn/problems/squares-of-a-sorted-array/description/publicstaticint[]sortedSquares(int[]nums){intleft=0;intright=nums.length-1;int[]result=newint[nums.length];intwrite=......
  • 最小生成树
    求一个图的最小生成树。本文不面向读者。一般是无向图？只考虑连通图。Kruskal贪心。将每条边的边权从小到大排序，依次加入边。用一个并查集维护点的连通情况，如果该边两个端点尚未连通，则选择此边，否则检查下一条边。当加入\(n-1\)条边后，算法结束。时间复杂度\(O(m\logm)\)......
  • 代码随想录算法训练营第三十八天| ● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯
    理论基础 代码随想录(programmercarl.com)动态规划的五部曲：确定dp数组（dptable）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组斐波那契数 题目链接：509.斐波那契数-力扣（LeetCode）思路：还好。classSolution{public:intfib(intn)......
  • 530. 二叉搜索树的最小绝对差c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/voidinorder(structTreeNode*root,int*t,int*pre){if(!root)return;inorder(root->left,t,pr......
  • 代码随想录算法训练营第三十八天 | 746. 使用最小花费爬楼梯，、70. 爬楼梯，509. 斐波那
     509.斐波那契数 已解答简单 相关标签相关企业 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0)=0，F(1)=1F(n)=F(n-1)+F(n-2)，其中n>......
  • 【C++】求二叉树的最大深度和最小深度
    //求一颗二叉树的最大深度求高度:后序遍历求深度:前序遍历intmaxDepth(TreeNode*root){returnroot?1+max(maxDepth(root->left),maxDepth(root->right)):0;}//求一颗二叉树的最小深度(实质上是后序遍历)intminDepth(TreeNode*root){if(!root)retur......
  • 111. 二叉树的最小深度c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/intmin(inti,intj){if(i<j)returni;returnj;}intminDepth(structTreeNode*root){......
  • 基于最小二乘正弦拟合算法的信号校正matlab仿真,校正幅度,频率以及时钟误差,输出SNDR,
    1.算法运行效果图预览    2.算法运行软件版本matlab2022a 3.算法理论概述        在信号处理领域，正弦信号是一种常见且重要的信号形式。然而，在实际应用中，由于各种噪声和失真的影响，正弦信号的幅度、频率和相位可能会发生偏差。为了准确地恢复和分析这些信......
  • 浅谈EK求网络流 & 最小费用最大流
    1.简介：网络流，指的是一种图上问题。首先我们要知道什么是网络。网络的性质如下：有且仅有一个点入度为0，且只有一个点出度为0，我们把入读为0的点叫做源点，出度为0的点为汇点。网络是一个有向图，且有边权。那么流是什么呢？考虑对于下面这个网络：其中\(s\)是源点，\(t\)......
  • PDF文件太大如何免费压缩到最小？
    又到了一年一度找工作高峰期了，为了防止发送的简历文档排版错乱，一般都是采用PDF格式。但有时在投递简历时，附上过大的附件（比如设计岗位），这样就会影响发送和对方打开查看的效率。那么pdf如何快速免费压缩大小呢？教你2个无需安装软件的简单方法。方法一：操作系统自带压缩功能这是一种......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99