算法竞赛部分算法（二）算法模板（C/C++）

整理于 NOIP2016 前 - 转载自我的博客 https://wzw21.cn/2021/07/26/algorithms2/

• 常用算法模板（C/C++）
• • 定义部分
  • 图论
  • • 存图
    • SPFA（最短路）
    • Dijkstra+堆优化（最短路）
    • Kruskal（最小生成树）
    • Tarjan（强连通分量）
    • Hungary（二分图匹配）
    • 拓扑排序
  • 数论
  • • 线筛（求素数与欧拉函数）
    • 快速幂
    • 扩展欧几里得
  • 树
  • • LCA（最近公共祖先）
    • 线段树
  • 排序
  • • 归并排序
    • 快速排序
  • 高精度
  • • 高精度乘法
  • 对拍（.bat）

#define MAXN 10005
#define MAXM 10005
using namespace std;
int n,m;
struct edge_ {int to,next,w;}edge[MAXM*2];
int first[MAXN],et;
int dis[MAXN],vis[MAXN];
int low[MAXN],dfn[MAXN],tim,belong[MAXN],now;
int p[MAXN],eu[MAXN];bool f[MAXN];
struct bian_ {int u,v,w;}bian[MAXM];
int fa[MAXN];
int root,from[MAXN];
int rd[MAXN];
int anc[MAXN][16],deep[MAXN];
int A[MAXN],B[MAXN],cnt;
queue  Q;
stack  S;
priority_queue  Q1;
priority_queue , greater  > Q2;
//优先队列重载运算符见Dijkstra算法

void add(int u,int v,int w) //邻接表（前向星）
{
	et++;
	edge[et].to=v;
	edge[et].w=w;
	edge[et].next=first[u];
	first[u]=et;
}
void get_graph(int o) //1 无向图 2 有向图  3 边集数组 
{
	cin>>n>>m;
	int i,j,u,v,w;
	if (o==1||o==2||o==4||o==5) 
	{
		for (i=1;i<=m;i++)
		{
			cin>>u>>v>>w;
			add(u,v,w);
			if (o==1) add(v,u,w);
			if (o==4) rd[v]++;
		}
    }
    if (o==3)
    {
    	for (i=1;i<=m;i++)
    	cin>>bian[i].u>>bian[i].v>>bian[i].w;
    }
}

void SPFA()
{
	get_graph(1);
    int i,j,u,v,w;
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	Q.push(1);
	vis[1]=1;
	while (!Q.empty())
	{
		u=Q.front();
		Q.pop();
		vis[u]=0;
		int b=first[u];
		while (b!=0)
		{
			v=edge[b].to;
			w=edge[b].w;
			if (dis[u]+w 
Dijkstra+堆优化（最短路） 
struct node
{
	int dis,id;
	bool operator < (const node &x) const
    {
        return x.dis < dis;
    }
};
priority_queue  Q3;
bool blue[MAXN];
int dist[MAXN];
void Dijkstra(int s)
{
    for (int i=1;i<=n;i++)
      dist[i]=1e10;
	dist[s]=0;
	node tmp;
	tmp.dis=0;tmp.id=s;
	Q3.push(tmp);
	int u,v,b;
    while(!Q3.empty())
    {
    	tmp=Q3.top();
		u=tmp.id;
		Q3.pop();
    	if (blue[u]) continue;
    	blue[u]=true;
    	b=first[u];
    	while (b)
    	{
    		v=edge[b].to;
    		if (dist[u]+edge[b].w 
Kruskal（最小生成树） 
bool cmp1(bian_ x,bian_ y)
{
   return x.w 
Tarjan（强连通分量） 
void tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	S.push(u);
	int v=0;
	vis[u]=1;
	int b=first[u];
	while (b!=0)
	{
		v=edge[b].to;
		if (dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if (vis[v]) low[u]=min(low[u],dfn[v]);
		b=edge[b].next;
	}
	if (dfn[u]==low[u])
	{
		now++;
		do{
			v=S.top();
			S.pop();
			belong[v]=now;
			vis[v]=0;
		}while (u!=v);
	}
}
void scc()
{
	memset(vis,0,sizeof(vis));
	get_graph(2);
	tarjan(1);
	for (int i=1;i<=n;i++)
	cout< 
Hungary（二分图匹配） 
bool match(int u)
{
	int b=first[u];
	while (b!=0)
	{
		int v=edge[b].to;
		if (vis[v]!=root)
		{
			vis[v]=root;
			if (!from[v]||match(from[v]))
			{
				from[v]=u;
				return true;
			}
		}
		b=edge[b].next;
	}
	return false;
}
void hungary()
{
	int x,y,ans=0;
	cin>>x>>y;
	get_graph(1);
	for (int i=1;i<=x;i++)
	{
	  root=i;
	  if (match(i)==1)
	  ans++;
    }
    cout< 
拓扑排序 
void tuopu()
{
	get_graph(4);
	int i,j,u,v;
	for (i=1;i<=n;i++)
	if (rd[i]==0) S.push(i);
	while (!S.empty())
	{
		u=S.top();
		S.pop();
		cout< 
数论 
线筛（求素数与欧拉函数） 
void prime()
{
	int i,j,pi=1;
	for (i=2;i 
快速幂 
void ksm()
{
	int a,b,c;
	cin>>a>>b>>c;
	int ans=1;
	while (b!=0)
	{
		if (b%2!=0) ans=ans*a%c;
		a=a*a%c;
		b/=2;
	}
	cout< 
扩展欧几里得 
int e_gcd(int a,int b,int &x,int &y)
{
	if (b==0) 
	{
		x=1;
		y=0;
		return a;
	}
	int ans=e_gcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return ans;
}
void exgcd()
{
	int a,b,x,y,gcd;
	cin>>a>>b;
	gcd=e_gcd(a,b,x,y);
	cout< 
树 
LCA（最近公共祖先） 
void dfs(int u,int s)
{
	int b=first[u];
	deep[u]=s;
	while (b!=0)
	{
		int v=edge[b].to;
		dfs(v,s+1);
		anc[v][0]=u;
		b=edge[b].next;
	}
}
int getlca(int a,int b)
{
	int i,j,k;
	if (deep[a]=0;k--)
	  if (deep[a]-(1<=deep[b])
		a=anc[a][k];
	if (a==b) return a;
	for (j=log(n)/log(2)+1;j>=0;j--)
	  if (anc[a][j]!=anc[b][j])
	  {
	  	a=anc[a][j];
	  	b=anc[b][j];
	  }
	return anc[a][0];
}
void lca()
{
	get_graph(4);
	int i,j,k;
	for (i=1;i<=n;i++)
	if (rd[i]==0) break;
	dfs(i,0);
	for (j=1;j<=log(n)/log(2)+1;j++)
	  for (k=1;k<=n;k++)
		anc[k][j]=anc[anc[k][j-1]][j-1];
	int x,y;
	cin>>x>>y;
	cout< 
线段树 
#define maxn 200002
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
struct Node 
{
    long long sum,lazy;
} T[maxn<<2];
void pushup(int o) 
{
    T[o].sum=T[o<<1].sum+T[o<<1|1].sum;
}
void pushdown(int l,int r,int o) 
{
    int mid=(l+r)>>1;
    T[o<<1].sum+=T[o].lazy*(mid-l+1);
    T[o<<1|1].sum+=T[o].lazy*(r-mid);
    T[o<<1].lazy+=T[o].lazy;
    T[o<<1|1].lazy+=T[o].lazy;
    T[o].lazy=0;
}
void build(int l,int r,int o) 
{
    if(l==r) 
	{
        scanf("%d",&T[o].sum);
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(o);
}
void update(int L,int R,int V,int l,int r,int o) 
{
    if(l==L&&r==R) 
	{
        T[o].lazy+=V;
        T[o].sum+=V*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    if(T[o].lazy) pushdown(l,r,o);
    if(R<=mid) update(L,R,V,lson);
    else if(L>mid) update(L,R,V,rson);
    else {
        update(L,mid,V,lson);
        update(mid+1,R,V,rson);
    }
    pushup(o);
}
long long query(int L,int R,int l,int r,int o) 
{
    if(l==L&&R==r)
        return T[o].sum;
    int mid=(l+r)>>1;
    if(T[o].lazy) pushdown(l,r,o);
    if(R<=mid) return query(L,R,lson);
    else if(L>mid) return query(L,R,rson);
    return query(L,mid,lson)+query(mid+1,R,rson);
}
 
排序 
归并排序 
void merge_sort(int l,int r)
{
	if(l==r)return;
	int m=(l+r)/2;
	merge_sort(l,m);
	merge_sort(m+1,r);
	int i=l,j=m+1,p=l;
	while(i<=m&&j<=r)
	{
		if(A[i]<=A[j])
		{
			B[p]=A[i];p++;i++;
		}
		else
		{
			B[p]=A[j];p++;j++;
			cnt+=m-i+1;
		}
	}
	while(i<=m) {B[p]=A[i];i++;p++;}
	while(j<=r) {B[p]=A[j];j++;p++;}
	for(int k=l;k<=r;k++) A[k]=B[k];
}
void merge()
{
	cin>>n;
	int i,j;
	for (i=1;i<=n;i++)
	cin>>A[i];
	merge_sort(1,n);
	cout< 
快速排序 
void qsort(int *a,int start,int end)
{
	if (start>=end) return;
	int i=start,j=end,key=a[start];
	while (i=key) j--;
		a[i]=a[j];
		while (i 
高精度 
高精度乘法 
hp cheng(hp a,hp b)
{
	hp c;
	memset(c.w,0,sizeof(c.w));
	c.w[0]=a.w[0]+b.w[0];
	for (int i=1;i<=a.w[0];i++)
	  for (int j=1;j<=b.w[0];j++)
	    {
	      c.w[i+j-1]+=a.w[i]*b.w[j];
	      c.w[i+j]+=c.w[i+j-1]/10;
	      c.w[i+j-1]%=10;
	    }
	while (c.w[c.w[0]]==0&&c.w[0]>1)
	  c.w[0]--;
	return c;
}
 
对拍（.bat） 
@echo off
for /l %%i in (1,1,100) do (
     data.exe %%i > ab.in
     ::type ab.in
     ab.exe < ab.in > ab.out
     ab_baoli.exe < ab.in > ab_baoli.out
     fc ab.out ab_baoli.out >nul
     if not errorlevel 1 ( echo AC ) else ( goto wa )
)
goto end
:wa (
echo WA
type ab.in
)
pause
:end
pause