算法竞赛部分算法（二）算法模板

常用算法模板（C/C++）

整理于 NOIP2016 前 - Written by WZW

定义部分

#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 <int> Q;
stack <int> S;
priority_queue <int> Q1;
priority_queue <int, vector <int>, greater <int> > 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;
    }
}

SPFA（最短路）

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<dis[v])
			{
				dis[v]=dis[u]+w;
				if (vis[v]==0) 
				{
					Q.push(v);
					vis[v]=1;
				}
			}
			b=edge[b].next;
		}
	}
	for (i=1;i<=n;i++)
	cout<<dis[i]<<" ";
}

Dijkstra+堆优化（最短路）

struct node
{
	int dis,id;
	bool operator < (const node &x) const
    {
        return x.dis < dis;
    }
};
priority_queue <node> 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<dist[v])
    		{
    			dist[v]=dist[u]+edge[b].w;
    			tmp.dis=dist[v];tmp.id=v;
			    Q3.push(tmp);
    		}
    		b=edge[b].next;
    	}
    }
}

Kruskal（最小生成树）

bool cmp1(bian_ x,bian_ y)
{
    return x.w<y.w;
}
int find(int x)
{
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void unionn(int x,int y)
{
	int x1=find(x),y1=find(y);
	if (x1!=y1) fa[x1]=y1;
}
void kruskal()
{
	get_graph(3);
	int i,j;
	sort(bian+1,bian+1+m,cmp1);
	int m1=0,mst=0;
	for (i=1;i<=n;i++)
	fa[i]=i;
	for (i=1;i<=m;i++)
	{
		if (find(bian[i].u)!=find(bian[i].v))
		{
			unionn(bian[i].u,bian[i].v);
			mst+=bian[i].w;
			m1++;
			if (m1==n-1) break;
        }
	}
	cout<<mst;
}

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<<belong[i]<<" ";
}

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

拓扑排序

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<<u<<" ";
		int b=first[u];
		while (b)
		{
			v=edge[b].to;
			rd[v]--;
			if (rd[v]==0) S.push(v);
			b=edge[b].next;
		}
	}
}

数论

线筛（求素数与欧拉函数）

void prime()
{
	int i,j,pi=1;
	for (i=2;i<MAXN;i++)
	{
		if (f[i]==0)
		{
			p[pi]=i;
			pi++;
			eu[i]=i-1;
		}
		for (j=1;j<pi&&i*p[j]<MAXN;j++)
		  {
		  	f[i*p[j]]=true;
		  	if (i%p[j]==0)
		  	{
		     	eu[i*p[j]]=eu[i]*p[j];
				break;
		  	}
		    else eu[i*p[j]]=eu[i]*(p[j]-1);
	      }
	}
	for (i=1;i<=1000;i++)
	cout<<p[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<<ans;
}

扩展欧几里得

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<<gcd<<" "<<x<<" "<<y<<endl;
	cout<<(x%b+b)%b<<endl;//gcd(a,b)=1时,x是a关于b的逆元
	//除以一个数取模等于乘以这个数的逆元取模。 
}

树

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]<deep[b]) swap(a,b);
	for (k=log(n)/log(2)+1;k>=0;k--)
	  if (deep[a]-(1<<k)>=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<<getlca(x,y);
}

线段树

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

快速排序

void qsort(int *a,int start,int end)
{
	if (start>=end) return;
	int i=start,j=end,key=a[start];
	while (i<j)
	{
		while (i<j && a[j]>=key) j--;
		a[i]=a[j];
		while (i<j && a[i]<key) i++;
		a[j]=a[i];
	}
	a[i]=key;
	qsort(a,start,i-1);
	qsort(a,i+1,end);
}
qsort(a,1,n);
//该代码块与定义部分无关

高精度

高精度乘法

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