首页 > 编程语言 >2023烟台7天编程集训笔记3

2023烟台7天编程集训笔记3

时间：2023-07-12 20:22:15浏览次数：51  
标签：dist int ed 短路 编程 vis edge 2023 集训

次小生成树：第二小的生成树。

次小生成树：删掉一条边，再加上一条边，使得差值尽量小，并且要是一个树。

次小生成树：如果一条边在最小生成树上，我们就叫他树边，如果不在最小生成树上就叫他非树边。

次小生成树：删掉一条树边，加上一条非树边。

次小生成树：倍增 LCA 询问环上最大的值（章鱼图）。

从一张 m 条边的图中找 n−1 条边，使得找出来的边和已有的点构成一棵树，组成的图就叫做原图的生成树。一个生成树的大小是选出来的所有边的边权之和。大小最小的生成树被称为 最小生成树。

生成树并查集的路径压缩

点击查看代码 
//O(mlogm) sort最慢 
#include<bits/stdc++.h>
using namespace std;

int to[MAXN];//to[i] 表示 i 点在并查集里面的箭头指向谁

int go(int p){//看一下点 p 沿着并查集箭头最后会走到哪里 
	//O(1) 
	if(to[p]==p)return p;//指向自己
	/*else{
		int q=go(to[p]);
		to[p]=q;
		return q;
	}*/
	else return to[p]=go(to[p]);
} 

struct edge{
	int s,e,d;
}ed[MAXN];//ed[i] 代表第 i 条边是在 s 与 e 之间的长度为 d 的边
 
int n,m;

bool cmp(edge a,edge b){
	return a.d<b.d;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>ed[i].s>>ed[i].e>>ed[i].d;
		
	sort(ed+1,ed+m+1,cmp);//所有边按照边权进行排序
	
	for(int i=1;i<=n;i++)
		to[i]=i;//初始化并查集
		
	int ans=0;//生成树大小
	int cnt=0;//边的数量
	for(int i=1;i<=m;i++){//O(m)
		if(cnt==n-1)break;
		int p1=ed[i].s,p2=ed[i].e,d=ed[i].d;
		if(go(p1)!=go(p2)){//不在同一个连通块
			ans+=d;
			to[go(p1)]=go(p2);
			++cnt;
		}
	}

	cout<<ans<<endl;
}

SPFA

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int> > z[500005];
int dist[500005];//dist[i] 代表从起点到 i 的最短路
bool vis[500005];//vis[i]代表 i 在不在队列里 
 
void add_edge(int s,int e,int d){
	z[s].push_back(make_pair(e,d)); 
}
int n,m,x;

void SPFA(int s){//以 s 作为起点算最短路 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int> q;//用来存可能改变其他点最短路的点
	q.push(s);
	vis[s]=true;
	while(!q.empty()){
		int p=q.front();
		q.pop();
		vis[p]=false;
		
		for(int i=0;i<z[p].size();i++){
			int e=z[p][i].first;
			int d=z[p][i].second;
			if(dist[e]>dist[p]+d){
				dist[e]=dist[p]+d;
				if(!vis[e])q.push(e),vis[e]=true;
			}
		}
	} 
}

signed main(){
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++){
		int s,e,d;
		cin>>s>>e>>d;
		add_edge(s,e,d);
	}
	
	SPFA(x);
	
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<' ';
	}
	return 0;
}

生成树

点击查看代码 
//O(nm) 
#include<bits/stdc++.h>
using namespace std;

int to[MAXN];//to[i] 表示 i 点在并查集里面的箭头指向谁

int go(int p){//看一下点 p 沿着并查集箭头最后会走到哪里 
	if(to[p]==p)return p;//指向自己
	else return go(to[p]);//递归调用 
} 

struct edge{
	int s,e,d;
}ed[MAXN];//ed[i] 代表第 i 条边是在 s 与 e 之间的长度为 d 的边
 
int n,m;

bool cmp(edge a,edge b){
	return a.d<b.d;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>ed[i].s>>ed[i].e>>ed[i].d;
		
	sort(ed+1,ed+m+1,cmp);//所有边按照边权进行排序
	
	for(int i=1;i<=n;i++)
		to[i]=i;//初始化并查集
		
	int ans=0;//生成树大小
	int cnt=0;//边的数量 
	for(int i=1;i<=m;i++){
		if(cnt==n-1)break; 
		int p1=ed[i].s,p2=ed[i].e,d=ed[i].d;
		if(go(p1)!=go(p2)){//不在同一个连通块 
			ans+=d;
			to[go(p1)]=go(p2);
			++cnt; 
		}
	}
	
	cout<<ans<<endl;		
}

Bellman_ford

点击查看代码 
//可以针对负数边权，但是更慢。
#include<bits/stdc++.h>
using namespace std;
int s[100005],d[1000005],e[1000005];
int n,m;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>s[i]>>e[i]>>d[i];
		
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			dist[e[j]]=min(dist[e[j]],dist[s[j]]+d[j]);
	return 0;
}

Dijkstra优化

点击查看代码 
//用堆
#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> z[100005];
int dist[100005];//dist[i] 代表从起点到 i 的最短路
bool vis[i];//vis[i]代表 i 的最短路有没有被求出来 
 
void add_edge(int s,int e,int d){
	z[s].push_back(make_pair(e,d)); 
}
int n,m;

void Dijkstra(int s){//以 s 作为起点算最短路 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	priority_queue<pair<int,int> > heap;
	//first 用来存距离的相反数
	//second 用来存点的编号
	
	for(int i=1;i<=n;i++)
		heap.push(make_pair(-dist[i],i)); 
	for(int i=1;i<=n;i++){
		//选一个 dist 最小的点
		while(vis[heap.top().second])
			heap.pop();
		int p=heap.top().second;
		heap.pop();
		vis[p]=true;
		 
		//用这个点去进行松弛操作 
		for(int j=0;j<z[p].size();j++){
			int q=z[p][j].first;
			int d=z[p][j].second;///这是一条从 p 到 q 长度为 d 的边
			if(dist[q]>dist[p]+d){
				dist[q]=dist[p+d];
				heap.push(make_pair(-dist[q],q)); 
			}
		}
	} 
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int s,e,d;
		cin>>s>>e>>d;
		add_edge(s,e,d);
	}
	
	Dijkstra(1);
	
	int T;
	cin>>T;
	while(T--){
		int x;
		cin>>x;
		cout<<dist[x]<<'\n';
	}
	return 0;
}

拓扑排序

点击查看代码 
//拓扑排序：针对 DAG。
//对有向图中的每一个点进行排序，使得最后的排序结果都是从左向右指的。
//不断删除入度为 0 的点，然后不断把入度为 0 的点加入答案。
//那如何删除一个点呢？其实不需要删除，只需要将入度减掉即可。
#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> z[100005];
//z[i] 代表所有以 i 为起点的边
//z[i][j] 代表以 i 为起点的第 j 条边
//z[i][j].first 代表以 i 为起点的第 j 条边的终点 
//z[i][j].second 代表以 i 为起点的第 j 条边的长度 
 
void add_edge(int s,int e,int d){//添加一个从 s 出发到 e 的长度为 d 的边 
	//push_back:向 vector 的末尾加入一个元素
	z[s].push_back(make_pair(e,d)); 
}
int n,m;
int in[100005];//in[i] 代表 i 点的入度 
int result[100005];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int s,e,d;
		cin>>s>>e>>d;//起点为s，终点为e，长度为d
		
		add_edge(s,e,d);
		in[e]++; 
	}
	
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(in[i]==0)result[++cnt]=i;
		
	for(int i=1;i<=n;i++){//当前要取出拓扑排序的结果中的第 i 个点 
		int p=result[i];
		for(int j=0;j<z[p].size();j++){
			int q=z[p][j];//p->q的边
			in[q]--;
			if(in[q]==0)result[++cnt]=q; 
		} 
	}	
}

多源最短路算法floyd原始版本

点击查看代码 
//O(n^3) n<=250
#include<bits/stdc++.h>
using namespace std;

int dist[1005][1005][1005];
//dist[i][j][k] 代表从 j 走到 k 使得中间经过的节点编号 <=i 的情况下的最短路
const int INF=0x3f3f3f3f;
int n,m;//n 点 m 边 

signed main(){
	memset(dist,0x3f,sizeof(dist));//把数组每一个元素赋值为INF 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,d;
		cin>>s>>e>>d;//一条从 s 到 e 长度为 d 的边
		dist[0][s][e]=min(dist[0][s][e],d); 
	} 
	
	for(int i=1;i<=n;i++)
		dist[0][i][i]=0;
		
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				dist[i][j][k]=min(dist[i-1][j][k],dist[i-1][j][i]+dist[i-1][i][k]);
	
	int T;
	cin>>T;
	while(T--){
		int i,j;
		cin>>i>>j;
		cout<<dist[n][i][j]<<'\n';
	}		
	return 0;
}

多源最短路算法floyd压维

点击查看代码 
//O(n^3) n<=250
//注意是无向图，所以存图时要存两次。
#include<bits/stdc++.h>
using namespace std;

int dist[1005][1005];
//dist[i][j][k] 代表从 j 走到 k 使得中间经过的节点编号 <=i 的情况下的最短路
const int INF=0x3f3f3f3f;
int n,m;//n 点 m 边 

signed main(){
	memset(dist,0x3f,sizeof(dist));//把数组每一个元素赋值为INF 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,d;
		cin>>s>>e>>d;//一条从 s 到 e 长度为 d 的边
		dist[s][e]=min(dist[s][e],d); 
	} 
	
	for(int i=1;i<=n;i++)
		dist[i][i]=0;
		
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
	
	int T;
	cin>>T;
	while(T--){
		int i,j;
		cin>>i>>j;
		cout<<dist[i][j]<<'\n';
	}		
	
	return 0;	
}

单源最短路:求一个起点到其他点的最短路，起点是固定的。

多源最短路:求多个起点到其他点的最短路，起点不固定。

单源最短路算法Dijkstra

点击查看代码 
//选一个最短路已经求好的点，选的点一定是当前 dist 最小的点。
//进行松弛操作（用自己的最短路去更新自己周围的最短路）。
#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> z[100005];
int dist[100005];//dist[i] 代表从起点到 i 的最短路
bool vis[i];//vis[i]代表 i 的最短路有没有被求出来 
 
void add_edge(int s,int e,int d){
	z[s].push_back(make_pair(e,d)); 
}
int n,m;

void Dijkstra(int s){//以 s 作为起点算最短路 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for(int i=1;i<=n;i++){
		//选一个 dist 最小的点
		int p=0;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&(p==0||dist[j]<dist[p]))p=j;
		vis[p]=true;
		 
		//用这个点去进行松弛操作 
		for(int j=0;j<z[p].size();j++){
			int q=z[p][j].first;
			int d=z[p][j].second;///这是一条从 p 到 q 长度为 d 的边
			dist[q]=min(dist[q],dist[p]+d);
		}
	} 
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int s,e,d;
		cin>>s>>e>>d;
		add_edge(s,e,d);
	}
	
	Dijkstra(1);
	
	int T;
	cin>>T;
	while(T--){
		int x;
		cin>>x;
		cout<<dist[x]<<'\n';
	}
	return 0;
}

标签：dist,int,ed,短路,编程,vis,edge,2023,集训
From： https://www.cnblogs.com/zhuyucheng929/p/17548734.html

相关文章

  • 你省（福建）省队集训 Day5 T3 乱搞分析
    简要题意有\(1\leT\le10^6\)次询问，每次询问正整数\(x,p\)，\(p\)为素数，令\(n=xp^2\)，问是否存在三个正整数\(a,b,c\)，满足\(ab+bc+ca=n\)。有的话给出构造，否则输出\(-1\)。solution打表注意到只有\(n=4,18\)是无解的。打表namespaceDB{ constintN=1e5; struc......
  • 【雕爷学编程】Arduino动手做（113）---5110液晶屏模块2
    37款传感器与执行器的提法，在网络上广泛流传，其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块，依照实践出真知（一定要动手做）的理念，以学习和交流为目的，这里准备逐一动手尝试系列实验，不管成功（程序走通）与否，都会记录下来---小小的进步或是......
  • 2023烟台7天编程集训笔记2
    倍增点击查看代码//最大值不支持减法操作//倍增代码，求区间的最大值#include<bits/stdc++.h>usingnamespacestd;intn,a[1000000],f[100000][20];//f的j次方开到20就可以达到1000000intx[100010];//x[i]代表长度为i的区间，用两个长度为2^x[i]的区间能够覆盖intmain()......
  • 每日总结2023年7月12日
    今日学习：信息系统安全属性：保密性（最小授权原则、防暴露、信息加密、物理保密）、完整性（安全协议、校验码、密码校验、数字签名、公证）、可用性（综合保障（IP过滤、业务流控制、路由选择控制、审计跟踪））、不可抵赖性（数字签名）；对称加密技术：加密和解密的密钥是完全一致的（加密强度不高、密钥分......
  • 2023.7.12
    学习java中的类面向对象与面向过程面向过程：强调的是功能行为，以函数为最小单位，考虑怎么做。面向对象：强调具备了功能的对象，以类/对象为最小单位类与对象的关系类：对一类事物的描述，是抽象的、概念上的定义对象：是实际存在的该类事物的每个个体，因而也称为实例(instance)面向对象......
  • 2022-2023 XCPC生涯总结
    参加比赛总结ICPC2022网络预选第一场2022.9.17队名沿用了去年yezi他们队的队名，这场因为有六级所以只有我们队和james_zhou队打.Caed开场过了CDH，开始写A，我一直在想L，240分钟左右我们分别把A和L过了，一起想G，Caed神中神最后把G想出来了。赛后知道是校排75，大概稳前100了，考虑到应......
  • 2023烟台7天编程集训笔记
    sort函数：把数组从小到大排序max函数：求出两个数的最大值min函数：求出两个数的最小值unique函数：使用前提是先排好序，再使用，效果是去重merge_sort归并排序reverse函数：翻转数组random_shuffle函数：把a[1]到a[n]随机打乱swap函数：交换两个数没有单调性不能二分位运算运行速度比加......
  • 2023河南萌新联赛第（一）场：河南农业大学 11/12
    晚来了一小时，终榜14名，血亏https://ac.nowcoder.com/acm/contest/61132A题不会，我选择oeisn=int(input())print(n*(n+1)*(n+2)//6%1000000007)python代码B题考虑线段树f[x][i][0]表示如果x所统辖的区间里，x第i位为0做计算得到的值，f[x][i][1]表示x所统辖的区间里，第i位为1做计......
  • Day08（2023.07.12）
    行程8:45    到达上海市信息安全测评认证中心（黄浦区陆家浜路1308号）9:00  学习《网络安全等级测评师培训教材》11:30--13:00   吃饭休息13:00 学习《网络安全等级测评师培训教材》17:00      下班 路由器：堡垒机：如......
  • Media Encoder 2023-视频编码软件mac/win版
    AdobeMediaEncoder2023是Adobe公司推出的一款专业的媒体编码和转换软件。作为AdobeCreativeCloud套件的一部分，它与其他Adobe创意应用程序（如PremierePro、AfterEffects）无缝集成，提供了一个强大的工具集，用于优化、转换和编码各种媒体文件。→→↓↓载MediaEncoder2......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99