首页 > 其他分享 >图论合集

图论合集

时间：2023-09-10 16:11:30浏览次数：60  
标签：图论 le int 短路 maxn push 合集 dis

最短路算法

全源最短路

问题

给出一张图 \(G\)，询问任意两点之间的最短路径。

Floyd 算法

我们令 \(f_{k,i,j}\) 为只能经过 \(1 \sim k\) 的节点的最短路。

那么初始化 \(f_{0,i,j}\) 为两点之间边权或者极大值。

容易得到 \(f_{k,i,j}=\min(f_{k,i,j},f_{k-1,i,x}+f_{k-1,x,j})\)。

那么 \(f_{n,u,v}\) 就是 \(u \to v\) 的最短路。

显然第一维对于答案没有影响，那么压掉之后空间就优化成了 \(O(n^2)\)。

时间复杂度 \(O(n^3)\)。

for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
		}
	}
}

单源最短路

Dijkstra 算法

Dijkstra 可以求出一个非负权边图的一个点 \(s\) 到其他所有点的最短路。

令 \(dis_i\) 为 \(s \to i\) 的最短路。

初始化所有 \(dis=\inf\)。

重复执行以下操作，直到每个点的最短路都确定：

  1. 从所有不确定最短路的点中，选取一个当前最短路最小的点，此时可以证明它的当前最短路就是它的最短路。

  2. 更新这个点的所有出边到达的所有点的 \(dis\)。（若当前点为 \(u\)，到达的点为 \(v\)，边权 \(w\)，则 \(dis_v=\min(dis_v,dis_u+w)\)。这个操作称作松弛操作。

时间复杂度为 \(O(n^2)\)。

Dijkstra 的堆优化

不难发现上述操作 \(1\) 可用堆进行优化。

将所有松弛到的点丢进一个堆里，每次取堆顶就可以了。

时间复杂度 \(O(n \log m)\)。

使用时需要根据图的性质来选择是否使用堆优化。

struct edge{
	int to,v;
};
struct node{
	int v,w;
	bool operator <(node a) const{
		return w>a.w;
	}
}wsy;
vector<edge> G[maxn]; 
priority_queue<node> q;
void wsyAKIOI(){
	dis[s]=0;
	wsy={s,0};
	q.push(wsy);
	while(q.size()){
		int u=q.top().v;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].to,val=G[u][i].v;
			if(dis[v]>dis[u]+val){
				dis[v]=dis[u]+val;
				if(!vis[v]){
					wsy={v,dis[v]};
					q.push(wsy);
				}
			}
		}
	}
}

Bellman-Ford 算法

上述提到了一个松弛式子：\(dis_u=\min(dis_u,dis_v+w)\)。

Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

不难发现每次操作时 \(O(m)\) 的。

由于一条最短路最多包含 \(n-1\) 条路径，所以循环最多执行 \(n-1\) 次。

时间复杂度 \(O(nm)\)。

Bellmax-Ford 算法较于 Dijkstra 的好处就是可以求含负权边图的最短路。

Bellman-Ford 的队列优化——SPFA

不难发现只有上一次被松弛的结点所连接的边才有可能引起下一次的松弛操作。

每次松弛操作的时候塞进一个队列里面，访问的就只有必要的边了。

void spfa(int s){
	q.push(s);
	inq[s]=114514;
	while(q.size()){
		int u=q.front();
		inq[u]=0;
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].e,w=G[u][i].v;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				} 
			}
		}
	}
}

由于 SPFA 可以被神奇数据卡到 \(O(nm)\)，所以没有负权边的时候还是用 Dijkstra 好。

应用

差分约束

差分约束，是由 \(n\) 个变量 \(x_1,x_2,x_3,\dots,x_n\) 以及 \(m\) 个约束条件组成的特殊 \(n\) 元一次不等式组，每个不等式（称为约束条件）形如

\[\boxed{x_i-x_j \le c_k(1 \le i,j \le n,i \neq j,1 \le k \le m)} \]

其中 \(c_k\) 为常数。

我们需要对这个 \(n\) 元一次不等式组求出任意一组解，或判断无解。

考虑如何来处理这个问题。

我们对约束条件 \(x_i-x_j \le c_k\) 变形为 \(x_i \le x_j+c_k\)，不难注意到这个式子与单源最短路中 \(dis_y \le dis_x+w\) 的式子不能说非常相似，只能说一模一样。

所以我们便可以对于每个约束条件，连一条 \(j \to i\) 的有向边，边权为 \(c_k\)。

因为我们的图可能不联通，所以我们需要建立一个超级源点 \(s\)，向每个点建立一条权值为 \(0\) 的有向边。由于有负权边，所以我们跑 SPFA。若途中存在负环，则该 \(n\) 元一次不等式组无解，否则，\(x_i=dis_i\) 即为该不等式组的一组解。

我们又不难注意到对于一组解中的每个数都加上一个常数，得到的仍然是该不等式组的一组解，因为这个常数在做差时会被消掉。

例1【模板】差分约束算法

差分约束模板题。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
const int maxn=5001;
struct node{
	int e,v;
};
vector<node> G[maxn+10];
int dis[maxn],cnt[maxn],vis[maxn];
queue<int> q;
bool spfa(int s){
	memset(dis,63,sizeof(dis));
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty()){
    	int u=q.front();
    	q.pop(),vis[u]=0;
    	for(int i=0;i<G[u].size();i++){
    		node ed=G[u][i];
      		int v=ed.e,w=ed.v;
      		if(dis[v]>dis[u]+w){
        		dis[v]=dis[u]+w;
        		cnt[v]=cnt[u]+1;
        		if(cnt[v]>n) return 0;
       			if(!vis[v]) q.push(v),vis[v]=1;
      		}
    	}
  	}
  	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		G[b].push_back((node){a,c});
	}
	for(int i=1;i<=n;i++){
		G[0].push_back((node){i,0});
	}
	if(!spfa(0)){
		puts("NO");
	}
	else{
		for(int i=1;i<=n;i++){
			cout<<dis[i]+114514<<" ";
  			//由于上文提到的性质所以这么做是没问题的
		}
	}
	return 0;
}

例2 小 K 的农场

对于第一种约束，列出不等式 \(x_a-x_b \ge c\)，变形可得到 \(x_b-x_a \le -c\)，所以对于第一种约束条件，连一条 \(a \to b\) 边权为 \(-c\) 的边。

对于第二种约束，列出不等式 \(x_a-x_b \le c\)，连一条 \(b \to a\) 边权为 \(c\) 的边。

对于第三种约束，列出等式 \(x_a=x_b\)，我们可以看做不等式 \(x_a-x_b \le 0\) 或 \(x_b-x_a \le 0\)。前者连一条 \(b \to a\) 的边，后者连一条 \(a \to b\) 的边，边权皆为 \(0\)。

然后 SPFA 即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5000+10;
int n,m,dis[maxn],inq[maxn],cnt[maxn];
struct edge{
	int e,v;
};
vector<edge> G[maxn];
queue<int> q;
bool spfa(int s){
	q.push(s);
	inq[s]=1;
	cnt[s]++;
	while(q.size()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].e,w=G[u][i].v;
			if(dis[v]>dis[u]+w){
				//cout<<"考虑对"<<u<<"->"<<v<<"松弛"<<endl; 
				dis[v]=dis[u]+w;
				//cout<<"松弛后为"<<dis[u]<<endl;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>n) return 0;
				if(!inq[v]){
					q.push(v);
					inq[v]=1;
				}
			}
		}
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(dis,0x7f,sizeof(dis));
	dis[0]=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int a,b,c;
			cin>>a>>b>>c;
			G[a].push_back((edge){b,-c});
		}
		if(op==2){
			int a,b,c;
			cin>>a>>b>>c;
			G[b].push_back((edge){a,c});
		}
		if(op==3){
			int a,b;
			cin>>a>>b;
			G[a].push_back((edge){b,0});
		}
	}
	for(int i=1;i<=n;i++){
		G[0].push_back((edge){i,0});
	}
	if(spfa(0)) puts("Yes");
	else puts("No");
	return 0;
}

例3 [1007]倍杀测量者

不难注意到对每个不等式取 \(\log\) 即可让乘法转换为加法。

\(x_i \ge (k-t) \times x_j\)

即可变形为

\(\log(x_i) \ge \log(k-t) + \log(x_j)\)。

显然不可能暴力枚举所有 \(t\)。

我们又双叒叕不难注意到答案序列显然有单调性。

所以二分即可，check 函数写个差分约束判一下就行。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
struct flag{
	int op,a,b,k;
}fl[maxn];
struct edge{
	int nxt,to,tag;
	double w;
}a[maxn<<1];
int n,s,t,c[maxn],fr[maxn],head[maxn],cnt,vis[maxn],gt[maxn];
double l=0,r=1e18,T=-1,dis[maxn];
queue<int> q;
void add(int x,int y,int tag,double w){
	a[++cnt]=(edge){head[x],y,tag,log2(w)};
	head[x]=cnt;
}
int check(double T){
    memset(head,0,sizeof head);
    memset(fr,0,sizeof fr);
	cnt=0;
    while(q.size()){
    	q.pop();
	}
    for(int i=1;i<=n;i++){
    	if(c[i]){
        	add(i,0,1,c[i]);
			add(0,i,0,c[i]);
		}
	}
    for(int i=1;i<=s;i++){
        int a=fl[i].a,b=fl[i].b,k=fl[i].k,op=fl[i].op;
		if(c[a]&&c[b]&&((op==1&&c[a]<c[b]*(k-T))||(op==2&&c[a]*(k+T)<c[b]))){
			return 1;
		} 
        if(op==1){
			add(a,b,1,k-T);
		}
        else{
        	add(a,b,0,k+T);
		}
    }
	for(int i=0;i<=n;i++){
		dis[i]=0;
		fr[i]=0;
		q.push(i);
		vis[i]=1;
	}
	while(q.size()){
		int x=q.front();
		for(int i=head[x];i;i=a[i].nxt){
			int u=a[i].to;
			double w;
			if(a[i].tag){
				w=dis[x]-a[i].w;
			}
			else{
				w=dis[x]+a[i].w;
			}
			if(dis[u]<=w&&dis[u]!=-1){
				goto luqyou;
			}
			dis[u]=w;
			fr[u]=fr[x]+1;
			if(fr[u]==n+2) return 1;
			if(!vis[u]){
				q.push(u);
				vis[u]=1;
			}
			luqyou:;
		}
		q.pop();
		vis[x]=0;
	}
    return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n>>s>>t;
    for(int i=1;i<=s;i++){
        int op,a,b,k;
		cin>>op>>a>>b>>k;
        fl[i]=(flag){op,a,b,k};
        if(op==1){
        	r=min(r,(double)k-1e-8);
		}
    }
    for(int i=1;i<=t;i++){
    	int x,y;
    	cin>>x>>y;
		c[x]=y;
	}
    while(r-l>1e-6){
        double mid=(l+r)/2.0;
        if(check(mid)){
        	l=mid;
        	T=mid;
		}
		else{
			r=mid;
		}
    }
    if(T==-1){
    	puts("-1"); 
	}
	else{
		printf("%.10lf",T);
	}
	return 0;
}

标签：图论,le,int,短路,maxn,push,合集,dis
From： https://www.cnblogs.com/luqyou/p/17691340.html

相关文章

  • 搜索合集
    深度优先搜索（DFS）引入：迷宫问题有一个\(n\timesm\)的迷宫，你一开始在\((1,1)\)，每次可以向上下左右走一步，要走到\((n,n)\)且路径不能重复，不能经过障碍，问有多少种方法？用以下迷宫为例：（红色是起点，绿色是终点）我们每次可以向上下左右走一步。这样，我们每次选择一个方向，沿着这个......
  • 人脸识别解决方案全套文件大合集，120份全新精选，有这个就够了
    一、人脸识别4个特点人脸识别和其他身份识别相比，有4个特点：1、便捷性。人脸是生物特征，不需要携带类似身份证的东西2、非强制性。识别的过程甚至不需要对象的配合，只要拍摄到人脸就可以进行识别，例如安防领域就是如此。3、非接触性。不需要跟设备进行接触，相比指纹更加安全一些。4、并行......
  • 2023-09-05 图论专项训练（五）
    我TM但凡有点水平也不至于一点水平没有吧。——每日感想T1距离/P4162[SCOI2009]最长距离这道题本质上是一道十分弱智的搜索题，无论是开DFS还是开BFS还是开BDFS都能做。本人在这里不建议使用使用deque进行BFS，理由是运行速度比较慢，稍有不慎就见祖宗了。我在这里使用DFS,但是纯......
  • 【专题】电动汽车充电基础设施建设与运营的优化解决方案报告PDF合集分享（附原数据表）
    原文链接：https://tecdat.cn/?p=336002022年，中国城市充电基础设施继续快速增长，总量从2021年的261.7万台增加到2022年的521万台，同比增幅超过99%。其中，私人充电桩的增加数量达到194.2万台，是公共充电桩增加数量的3倍，私人充电桩占比也从2021年的56.2%增加到2022年的65.5%。阅读原文，获......
  • 线性筛合集
    线性筛合集1.线性筛素数voidinit(){ispri[1]=true;for(inti=2;i<=n;i++){if(!ispri[i])pri[++cnt]=i;for(intl=1;l<=cnt&&i*pri[l]<=n;l++){ispri[i*pri[l]]=true;if(i%pri[l]==0)break......
  • PG索引失效合集
    通常来说，优化器分为两种，一种是CBO，即Cost-BasedOptimizer的缩写，直译过来就是“基于成本的优化器”。一种是RBO，是Rule-BasedOptimizer的缩写，直译过来就是“基于规则的优化器”在得到最终的执行计划时，RBO会根据一组内置的规则，去选择执行计划，这就导致了RBO选择的执行计划可能不是最......
  • 即时通讯技术文集（第19期）：IM架构设计基础知识合集 [共13篇]
    为了更好地分类阅读52im.net总计1000多篇精编文章，我将在每周三推送新的一期技术文集，本次是第19 期。[-1-] 微信后台基于时间序的新一代海量数据存储架构的设计实践[链接] http://www.52im.net/thread-2970-1-1.html[摘要] 时隔3年，微信再次分享了基于时间序的新一代海量数据存......
  • 【HMS Core】推送热门合集
    【问题描述1】推送消息成功，但只收到两条，其余收不到【解决方案】1、您是否开通了消息自分类，因为现在是有咨询营销类消息限制的。没有使用自分类权益的话默认是资讯营销类消息。推送数量管理细则参考2、您可以通过申请自分类权益，来使用服务与通讯类消息，这种是没有这个限制的消息分类......
  • 即时通讯技术文集（第19期）：IM架构设计基础知识合集 [共13篇]
    为了更好地分类阅读52im.net总计1000多篇精编文章，我将在每周三推送新的一期技术文集，本次是第19 期。[-1-] 微信后台基于时间序的新一代海量数据存储架构的设计实践[链接] http://www.52im.net/thread-2970-1-1.html[摘要] 时隔3年，微信再次分享了基于时间序的新一代海量......
  • Androd 7.0编译错误合集
    1 error:ro.build.fingerprintcannotexceed91bytesbuild/tools/post_process_props.py.Changelinesasfollows:PROP_NAME_MAX=31#PROP_VALUE_MAX=91PROP_VALUE_MAX=128PROP_NAME_MAX=31#PROP_VALUE_MAX=91PROP_VALUE_MAX=128bionic/libc/include......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99