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

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

时间：2023-07-12 19:22:44浏览次数：41  
标签：std dist int 代码 编程 namespace cin 2023 集训

倍增

点击查看代码 
//最大值不支持减法操作
//倍增代码，求区间的最大值
#include <bits/stdc++.h>
using namespace std;
int n,a[1000000],f[100000][20];//f的j次方开到20就可以达到1000000
int x[100010];//x[i]代表长度为i的区间，用两个长度为2^x[i]的区间能够覆盖
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
	    cin>>a[i];
    }
    x[i]=0;
    for(int i=2;i<=n;i++)
    {
	    x[i]=x[i>>1]+1;//x[111]=x[55]+1;
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
	    cin>>l>>r;
	    int len=r-l+1;
	    int j=x[len];
	    cout<<max(f[l][x[len]],f[r-(1<<x[len])+1][x[len]]);
    }
    for(int i=1;i<=n;i++)
    {
	    f[i][0]=a[i]; 
    }
    for(int j=1;(1<<j)<=n;j++)
    {
	    for(int i=1;i+(1<<j)-1<=n;i++) 
	    {
	    	f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	    } 
    }
    return 0;
}

二分

点击查看代码 
//二分代码
#include <bits/stdc++.h>
using namespace std;
int a[100010],n,m;
int main()
{
	cin>>n; 
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		int l=0,r=n;//代表当前x可能出现的范围是l+1~r 
		while(l+1!=r)
		{
			int m=(l+r)>>1;
			if(x<=a[m])
			{
				r=m;//当前答案区间，从l+1~r，变为l+1~m 
			}
			else
			{
				l=m;
			 } 
		 } 
		 if(a[r]==x) 出现过; else 没出现过; 
	}
	return 0;
 }

快速幂

点击查看代码 
//快速幂代码 
int ksm(int x,int y,int p)//计算x^y%p 
{
	if(y==0)
	{
		return 1;
	}
	int z=ksm(x,y/2,p);//z=x^(y/2)%p
	z=1ll*z*z%p;
	if(y&1)
	{
		z=1ll*z*x%p;
	}
	return z;
}

矩阵乘法

点击查看代码 
//矩阵乘法 
struct matrix
{
	int n,m;//行数，列数 
	int n[5][5];//矩阵里每一个数是多少
	matrix()
	{
		n=m=0;
		memset(z,0,sizeof(a));
	}
};
matrix operator*(const matrix &m1,const matrix &m2)//计算m1*m2
{
 	matrix m3;
 	m3.n=m1.n; m3.m=m2.m;
 	for(int i=1;i<=m3.n;i++)
 	{
 		for(int j=1;j<=m3.m;j++)
 		{
 			for(int k=1;k<=m1.m;k++)
 			{
 				m3.a[i][j]+=m1.a[i][k]*m2.a[k][j];
			}
		}
	}
	return m3;
} 
调用:m3=m1*m2;

矩阵斐波那契数列

点击查看代码 
//矩阵斐波那切数列 
#include <iostream>
using names
struct matrix
{
	int n,m;//行数，列数 
	int a[5][5];//矩阵里每一个数是多少
	matrix()
	{
		n=m=0;
		memset(z,0,sizeof(a));
	}
};
matrix operator*(const matrix &m1,const matrix &m2)//计算m1*m2
{
 	matrix m3;
 	m3.n=m1.n; m3.m=m2.m;
 	for(int i=1;i<=m3.n;i++)
 	{
 		for(int j=1;j<=m3.m;j++)
 		{
 			for(int k=1;k<=m1.m;k++)
 			{
 				m3.a[i][j]+=m1.a[i][k]*m2.a[k][j];
			}
		}
	}
	return m3;
} 
matrix ksm(matrix x,int y)//矩阵x^y=?
{
	if(y==0)
	{
		matrix z;
		z.n=z.m=x.n;
		for(int i=1;i<=z.n;i++)
		{
			z.a[i][i]=1;
		} 
		return z;
	}
	matrix z=ksm(x,y/2);
	z=z*z;
	if(y&1) z=z*x;
	return z;
} 
int main()
{
	cin>>n;
	matrix A;//[f0,f1]
	A.n=1;A.m=2;
	A.a[1][1]=0;A.a[1][2]=1;
	matrix B;
		A.n=1;A.m=2;
	B.a[1][1]=0;B.a[1][2]=1;
	B.a[2][1]=0;B.a[2][2]=1;
	matrix C=A*ksm(B,n);//[fn,fn+1]
	cout<<C.a[1][1]<<endl;
	return 0;
}

bfs

点击查看代码 
//bfs搜索
#include <iostream>
using namespace std; 
int n,m,a[10010][10010],sx,sy,tx,ty;
int step[maxn][maxn];//step[i][j]，代表从起点走到（i,j）需要多少步 
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main()
{
	cin>>n>>m;//行数，列数 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];//a[i][j]==1代表障碍物 
		}
	}
	cin>>sx>>sy;//起始坐标 
	cin>>tx>>ty;//终点坐标
	memset(step,-1,sizeof(step));
	step[sx][sy]=0;
	queue<pair<int,int> > q;//用来存能够向外进行扩展step的点 
	q.push(make_pair(sx,sy));
	while(q.size())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();//当前的点为(x,y)
		for(int i=0;i<4;i++)//枚举上下左右四个方向 
		{
			int xx=x+dx[i];
			int yy=y+dy[i];//从(x,y)走到了(xx,yy)
			if(xx>=1&&xx<=n&&yy>=1&&y<=m&&a[xx][yy]!=1&&step[xx][yy]==-1)
			{
				step[xx][yy]=step[x][y]+1;
				q.push(make_pair(xx,yy));
			}
			step[xx][yy]=step[x][y]+1;
			q.push(make_pair(xx,yy));
		}
	}
}

dfs

点击查看代码 
//dfs搜索 
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010];
int ans=-114514;
void dfs(int now,int nownum,int nowsum)//当前要看第now个元素选不选，已经选了nownum个数，已经选了的数的和是nowsum 
{
	if(now>n)
	{
		if(nownum==m) ans=max(ans,nowsum);
		return; 
	}
	dfs(now+1,nownum,nowsum);//不选 
	dfs(now+1,nownum+1,nowsum+a[now]);//选 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	} 
	dfs(1,0,0);
	cout<<ans;
	return 0;
}

dfs可行性剪枝优化

点击查看代码 
//dfs可行性剪枝优化
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010];
int ans=-114514;
void dfs(int now,int nownum,int nowsum)//当前要看第now个元素选不选，已经选了nownum个数，已经选了的数的和是nowsum 
{
    if(nownum>m) return;//可行性剪枝 
	if(nownum+n-now+1<m) return;
	if(now>n)
	{
		if(nownum==m) ans=max(ans,nowsum);
		return; 
	}
	dfs(now+1,nownum,nowsum);//不选 
	dfs(now+1,nownum+1,nowsum+a[now]);//选 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	} 
	dfs(1,0,0);
	cout<<ans;
	return 0;
}

dfs最优性剪枝优化

点击查看代码 
//dfs最优性剪枝优化
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010];
int ans=-114514;
void dfs(int now,int nownum,int nowsum)//当前要看第now个元素选不选，已经选了nownum个数，已经选了的数的和是nowsum 
{
    if(nowsum+sum[n]-sum[now-1]<=ans) return;//最优性剪枝
	if(now>n)
	{
		if(nownum==m) ans=max(ans,nowsum);
		return; 
	}
	dfs(now+1,nownum,nowsum);//不选 
	dfs(now+1,nownum+1,nowsum+a[now]);//选 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	} 
	dfs(1,0,0);
	cout<<ans;
	return 0;
}

用负数下标

点击查看代码 
//用负数下标
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[1000005];
int *b=a+500000; 
signed main(){
	b[-233];//指向 a[500000 - 233] 
	//b 的范围为 -500000 ~ 500000]; 
}

手写队列

点击查看代码 
//手写队列
#include<bits/stdc++.h>
using namespace std;
struct shouxie_queue{
	int z[1000005];
	int head;//第一个人在什么位置 
	int tail;//最后一个人在什么位置
	shouxie_queue(){//构造函数 
		head=1;
		tail=0;
		memset(z,0,sizeof(z)); 
		//memset(z,1,sizeof(z)) 
		//可以用的：-1 0x3f 0x3f3f3f3f（无穷大） 
	}
	void push(int x){
		z[++tail]=x;
	}
	void pop(){//在外面调用时判空 
		head++; 
	}
	int front(){
		return z[head];
	}
	int size(){
		return tail-head+1;
	}
};

双向bfs

点击查看代码 
//双向bfs 
#include<iostream>
using namespace std;
int a[4][4],b[4][4];
int step[87654321+1];//step[i] 代表走到状态i所需要的最小步数 
int belong[87654321+1];
//belong[i]==0 代表这个状态还没有被搜到
//belong[i]==1 代表这个状态是从起点被搜到的
//belong[i]==2 代表这个状态是从终点被搜到的 
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[9];//vis[i]i这个数有没有出现过 
int main()
{
	int s=0;
	for (int i=1;i<=3;i++)
		for (int j=1;j<=3;j++)
		{
			cin >> a[i][j];
			if (i!=3 || j!=3) s=s*10 + a[i][j];
		}
	memset(step,-1,sizeof(step));
	step[s] = 0; belong[s] = 1;
	step[12345678]=0; belong[12345678] = 2;
	queue<int> q;
	q.push(s);
	q.push(12345678); 
	while (q.size())
	{
		int s=q.front();
		int cur_step = step[s];
		int cur_belong = belong[s];
		q.pop();
		int x,y;
		memset(vis,false,sizeof(vis));
		for (int i=3;i>=1;i--)
			for (int j=3;j>=1;j--)
				if (i!=3 || j!=3)
				{
					a[i][j] = s%10;
					s=s/10;
					vis[a[i][j]] = true;
				}
		for (int i=0;i<9;i++)
			if (!vis[i]) a[3][3] = i;
		for (int i=1;i<=3;i++)
			for (int j=1;j<=3;j++)
				if (a[i][j]==0) x=i,y=j;
		for (int d=0;d<4;d++)
		{
			int xx=x+dx[d];
			int yy=y+dy[d];//(x,y) 和 (xx,yy)交换
			if (xx>=1 && xx<=3 && yy>=1 && yy<=3)
			{
				swap(a[x][y],a[xx][yy]);
				s=0;
				for (int i=1;i<=3;i++)
					for (int j=1;j<=3;j++)
						if (i!=3 || j!=3) s=s*10+a[i][j];
				if (step[s] == -1)
				{
					step[s] = cur_step+1;
					belong[s] = cur_belong;
					q.push(s);
				}
				else
				{
					if (belong[s] != cur_belong)
					{
						ans = cur_step + 1 + step[s];
						cout << ans << endl;
						exit(0);
					}
				}
				swap(a[x][y],a[xx][yy]);
			} 
		}
	}
	cout << step[12345678] << endl;
}

**单源最短路算法Dijkstra**

<details>
<summary>点击查看代码</summary>

//单源最短路算法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;

}

</details>

**flogd押维**

<details>
<summary>点击查看代码</summary>

//flogd押维 时间复杂度：O(n^3)

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;
}

</details>


**多源最短路算法flogd的代码：原始版本**

<details>
<summary>点击查看代码</summary>

//多源最短路算法flogd的代码：原始版本 时间复杂度是：O(n^3)

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;

}

</details>


**存图代码:编表**

<details>
<summary>点击查看代码</summary>

//存图代码:编表 优点是省内存，缺点是慢

include <bits/stdc++.h>

using namespace std;
int n,m,z[100010];
vector< pair<int,int> >z[maxn];//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的边
{
z[s].push_back(make_pair(e,d));
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int s,e,d;//起点s，终点e，长度d
cin>>s>>e>>d;
add_edge(s,e,d);
add_edge(e,s,d);
}

for(int i=1;i<=n;i++)
{
	for(int j=0;j<z[i].size();j++)
	{
		int e=z[i][j].first;
		int d=z[i][j].second;
		
	}
} 
return 0;

}

</details>


**存图代码：邻接矩阵**

<details>
<summary>点击查看代码</summary>

//存图代码：邻接矩阵 缺点是消耗空间大，优点是简单，快

include <bits/stdc++.h>

using namespace std;
int z[101][101];//z[i][j]代表从i到j那条边的长度

int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int s,e,d;
cin>>s>>e>>d;//起点为s,终点为e，长度为d的边

	z[s][e]=d; 
	//如果要存无向图加上z[e][s]=d;
}
return 0;

}

</details>


**拓扑排序**

<details>
<summary>点击查看代码</summary>

染色法：把一个点染色为 1，然后一层一层向外染色。如果一条边连接的两个点的颜色一样，就说明不是二分图，否则就是。
拓扑排序：针对 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; 
	} 
}

return 0;
}

</details>

**Dijkstra优化**

<details>
<summary>点击查看代码</summary>

//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;

</details>


**Bellman_ford**

<details>
<summary>点击查看代码</summary>

//可以针对负数边权，但是更慢。

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]);

}

</details>


**SPFA**

<details>
<summary>点击查看代码</summary>

//维护能改变其他点最短路的点的队列，直至队列为空。

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 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;

}

</details>

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

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

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

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

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

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

**最小生成树基础算法**

<details>
<summary>点击查看代码</summary>

//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;

}

</details>


**最小生成树并查集的路径压缩**

<details>
<summary>点击查看代码</summary>

//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;

}

</details>

标签：std,dist,int,代码,编程,namespace,cin,2023,集训
From： https://www.cnblogs.com/zhuyucheng929/p/17548591.html

相关文章

  • 每日总结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......
  • InDesign 2023-排版设计软件mac/win版
    AdobeInDesign2023是一款专业的排版设计软件，由Adobe公司开发。它是AdobeCreativeCloud套件中的一部分，为用户提供了丰富的工具和功能，用于创建出版物、印刷品、数字杂志、互动PDF和电子书等。→→↓↓载InDesign2023mac/win版 以下是InDesign2023的详细介绍：......
  • Python异步编程
    协程不是计算机提供,程序员人为创造也称为微线程,是一种上下文切换技术(通过一个线程实现代码块互相切换执行)普通代码的执行流程自上而下顺序执行deffun1():print(1)#...print(2)deffun2():print(3)#...print(4)fun1()fun2()-结......
  • HHHOJ #1238. 「NOIP 2023 模拟赛 20230712 D」但战斗还未结束 思考--zhengjun
    赛时想写60pts，结果cxr似乎少算了一点空间，导致我一直没把空间卡过去QWQ。当时不会dfs求拓扑序，这里讲一下。枚举所有非访问过的点依次dfs，每次进行下列操作：找出\(v\)的一个未访问过的入点\(u\)，调用dfs(u)；找不到\(u\)的时候，把\(v\)加入拓扑序列中。代码#inc......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99