模板集

标签：GCC ch int pragma optimize 模板 define

前言：

洛谷、博客园、CSDN 同步更新

博客园可能食用更佳

Part 0 缺省源 & 卡常

Part 0.1 火车头

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

Part 0.2 宏定义

#define re register
#define il inline
#define ls u<<1
#define rs u<<1|1
#define lowbit(x) (x&-x)
#define PII pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define clear(x) memset(x,0,sizeof(x))
#define ll long long
#define ld long double
#define pi acos(-1.0)

Part 0.3 快读快写

#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
char buf[1<<20],*p1,*p2;
template <typename T>
il void read(T &x)
{
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x*=f;
}
template <typename T>
il void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
il char getc()
{
	char ch=getchar();
	while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
	return ch;
}

Part 1 最短路

Part 1.1 Floyd

B3647 【模板】Floyd

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

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=105;
int n,m,dis[N][N];
template <typename T>
il void read(T &x)
{
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x*=f;
}
void Floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i^j&&i^k&&j^k&&dis[i][k])
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
	read(n),read(m);
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++) dis[i][i]=0;
	for(int i=1,u,v,w;i<=m;i++)
	{
		read(u),read(v),read(w);
		dis[u][v]=dis[v][u]=min(dis[u][v],w);
	}
	Floyd();
	for(int i=1;i<=n;i++,puts(" "))
		for(int j=1;j<=n;j++)
			printf("%d ",dis[i][j]);
	return 0;
}

Part 1.2 Dijkstra

1.2.1 无优化 Dijkstra

P3371 【模板】单源最短路径（弱化版）

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

#include<bits/stdc++.h>
#define il inline
#define pb push_back
using namespace std;
const int N=1e4+5,INF=2147483647;
int n,m,s,dis[N];
bool vis[N];
struct Edge
{
	int v,w;
};
vector<Edge> g[N];
template <typename T>
il void read(T &x)
{
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x*=f;
}
void Dijkstra(int s)
{
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0;
	for(int i=1;i<n;i++)
	{
		int mindis=INF,u;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&mindis>dis[j])
				mindis=dis[j],u=j;
		vis[u]=1;
		for(auto [v,w]:g[u])
			if(!vis[v]&&dis[v]>mindis+w)
				dis[v]=mindis+w;
	}
}
int main()
{
	read(n),read(m),read(s);
	for(int i=1,u,v,w;i<=m;i++)
	{
		read(u),read(v),read(w);
		g[u].pb((Edge){v,w});
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}

1.2.2 堆优化 Dijkstra

P4779 【模板】单源最短路径（标准版）

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

#include<bits/stdc++.h>
#define il inline
#define PII pair<int,int>
#define mp make_pair
#define fi fisrt
#define se second
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,m,s,dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;
struct Edge
{
	int v,w;
};
vector<Edge> g[N];
template <typename T>
il void read(T &x)
{
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x*=f;
}
void Dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0,q.push(mp(0,s));
	while(!q.empty())
	{
		int u=q.top().se;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto [v,w]:g[u])
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v]) q.push(mp(dis[v],v));
			}
	}
}
int main()
{
	read(n),read(m),read(s);
	for(int i=1,u,v,w;i<=m;i++)
	{
		read(u),read(v),read(w);
		g[u].pb((Edge){v,w});
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}

标签：GCC,ch,int,pragma,optimize,模板,define
From： https://www.cnblogs.com/lunjiahao/p/18560792/template