JZTXT

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

发布时间 2023-07-12 20:18:56作者: zhuyucheng

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

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

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

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

次小生成树：倍增 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;
}