模板补全计划

本文最后更新于：2024年9月13日 早上

数据结构

线段树

区间加乘

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define maxn 100010
#define LL long long  
#define left l,mid,k<<1
#define right mid+1,r,k<<1|1
#define lef k<<1 
#define rig k<<1|1
using namespace std;
int n,m,p,s,x,y;
long long sum[maxn*4],kk,lazy_ad[maxn*4],lazy_mu[maxn*4];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1; ch=getchar();}
	while(ch<='9'&&ch>='0') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void build(int l,int r,int k)
{
	lazy_mu[k]=1;
	if(l==r) sum[k]=read();
	else
	{
		int mid=(l+r)>>1;
		build(left); build(right);
		sum[k]=(sum[lef]+sum[rig])%p;//
	}
	return ;
}
inline void push(int l,int r,int k,LL a,LL b)
{
	lazy_ad[k]=(lazy_ad[k]*b+a)%p;
	lazy_mu[k]=(lazy_mu[k]*b)%p;
	sum[k]=(sum[k]*b+(r-l+1)*a)%p;
}
inline void down(int l,int r,int k)//
{
	int mid=(l+r)>>1;
	push(left,lazy_ad[k],lazy_mu[k]);
	push(right,lazy_ad[k],lazy_mu[k]);
	lazy_ad[k]=0;	lazy_mu[k]=1;
	return ;
}
inline void midefy(int l,int r,int k,LL a,LL b)
{
	if(x<=l&&r<=y) 	push(l,r,k,a,b);
	else
	{
		if(lazy_ad[k]!=0||lazy_mu[k]!=1) down(l,r,k);
		int mid=(l+r)>>1;
		if(x<=mid) midefy(left,a,b);
		if(y>mid) midefy(right,a,b);
		sum[k]=(sum[lef]+sum[rig])%p;
	}
	return ;
}
inline LL ask(int l,int r,int k)//询问
{
	if(x<=l&&r<=y) 	return sum[k];
	if(lazy_ad[k]!=0||lazy_mu[k]!=1) down(l,r,k);
	int mid=(l+r)>>1;
	LL ans=0;
	if(x<=mid) ans=(ans+ask(left))%p;
	if(y>mid) ans=(ans+ask(right))%p;
	return ans;
}
int main()
{
	n=read(); m=read(); p=read(); 
	build(1,n,1);
	while(m--)
	{
		s=read();x=read(); y=read();
		if(s==1)//add
		{
			kk=read(); 
			midefy(1,n,1,0,kk);
		}
		else if(s==2)//mul
		{
			kk=read(); 
			midefy(1,n,1,kk,1);
		}
		else printf("%lld\n",ask(1,n,1));//ask
	}
	return 0;
}

树状数组

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>  
#include<cmath>  
#include<cstring>  
#include<algorithm> 
using namespace std; 
inline int lowbit(int k){return k&(-k);}
int a[5000],c[5000],s[5000],n,m,m1,m2;
int add(int k,int yu)
{
	for(int kl=yu;kl<=n;kl+=lowbit(kl))
		c[kl]+=k;
	return 0;
}
int Find(int k)
{
	int sum=0;
	for(int kl=k;kl>0;kl-=lowbit(kl))
		sum+=c[kl];
	return sum;
}
int quadd(int k,int kl)
{
	for(int i=k;i>0;i-=lowbit(i))
		s[i]+=kl;
	return 0;
}
int quFind(int k)
{
	int sum=0;
	for(int kl=k;kl<n;kl+=lowbit(kl))
		sum+=s[kl];
	return sum;
}
int main()
{
	cin>>n>>m>>m1>>m2;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		add(a[i],i);
	}
	for(int i=1;i<=m1;i++)//单点修改
	{
		int kl,kl1;
		cin>>kl>>kl1;
		add(kl1-a[kl],kl);
	}
	for(int i=1;i<=m;i++)//区间求和
	{
		int x,y;
		cin>>x>>y;
		cout<<Find(y)-Find(x-1)<<endl;
	}
	////////////////////////////////////////////
	for(int i=1;i<=m1;i++)//区间修改
	{
		int kl,kl1,kl2;
		cin>>kl1>>kl2>>kl;
		quadd(kl2,kl);
		quadd(kl1-1,-kl);
	}
	for(int i=1;i<=n;i++)//输出区间修改后结果
		cout<<a[i]+quFind(i)<<' ';
	cout<<endl;
	////////////////////////////////////////////
	
	return 0;
}

图论

最小生成树

prim

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
using namespace std;
int n,a[5000][5000],m,sum=0;
int prim(int st)
{
	int dis[10000],vis[10000];
	memset(dis,10,sizeof(dis));
	for(int i=1;i<=n;i++)
		dis[i]=a[st][i];
	memset(vis,0,sizeof(vis));
	vis[st]=1;
	sum=0;
	for(int i=2;i<=n;i++)
	{
		int minn=dis[0],kl=0;
		for(int j=1;j<=n;j++)
		{
			if(vis[j]==0&&dis[j]<minn)
			{
				minn=dis[j];
				kl=j;
			}
		}
		vis[kl]=1;
		for(int j=1;j<=n;j++)
		{
			if(a[kl][j]<dis[j]&&vis[j]==0)
			{
				dis[j]=a[kl][j];
			}
		}
		sum+=minn;
	}
}
int main()
{
	//freopen("a1.in","r",stdin);
	//freopen("a1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
	}
	prim(1);
	cout<<sum<<endl;
	return 0;
}

Kruskal

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
struct nn
{
	int x,y,v;
};
struct ss
{
	int next,id,y,v;
}bian[50010];
nn bianpai[50010];
int mycmp(nn a1,nn a2){return a1.v<a2.v;}
int lin[50010],k=0,n,m,numn=0,sum=0;
int bianrank[50010],fa[50010],dd[50010];
void insert(int xx,int yy,int vv)
{
	//cout<<vv<<endl;
	bian[++k].y=yy,bian[k].id=xx,bian[k].v=vv;
	bian[k].next=lin[xx];
	lin[xx]=k;
}
int findfather(int xx)
{
	if(fa[xx]==xx)return xx;
	return fa[xx]=findfather(fa[xx]);
}
void addfather(int xx,int yy)
{
	int xfa=findfather(xx),yfa=findfather(yy);
	fa[xfa]=yfa;
}
int main()
{
	memset(dd,0,sizeof(dd));
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1,xx,yy,vv;i<=m;i++)//先用一个结构体存储每一条边用于排序
	{
		cin>>xx>>yy>>vv;
		bianpai[i].x=xx;
		bianpai[i].y=yy;
		bianpai[i].v=vv;
	}
	sort(bianpai+1,bianpai+m+1,mycmp);//将边从小到大排序
	for(int i=1;i<=m;i++)//将排好序的边用连接表按次序储存
	{
		//cout<<bianpai[i].v<<endl;
		insert(bianpai[i].x,bianpai[i].y,bianpai[i].v);
		insert(bianpai[i].y,bianpai[i].x,bianpai[i].v);
		bianrank[i]=k;//通过名次得到连接表中边的下标（由于连接表的构造性质可知实际上就是边的rank*2
	}
	//cout<<endl;
	for(int i=1,xfa,yfa;i<=m;i++)
	{
		xfa=findfather(bian[bianrank[i]].id);
		yfa=findfather(bian[bianrank[i]].y);
		if(xfa==yfa)continue;//判断这条边的两点是否在并查集中，若都存在则continue
		else
		{
			addfather(bian[bianrank[i]].id,bian[bianrank[i]].y);//将两点加入并查集中
			//cout<<bian[bianrank[i]].id<<' '<<bian[bianrank[i]].y<<' '<<bian[bianrank[i]].v<<endl;
			sum+=bian[bianrank[i]].v;
			if(dd[bian[bianrank[i]].id]==0)dd[bian[bianrank[i]].id]=1,numn++;//新点则计数器++
			if(dd[bian[bianrank[i]].y]==0)dd[bian[bianrank[i]].y]=1,numn++;//新点则计数器++
		}
		if(numn==n)//若n个点全在点集中，break
			break;
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<endl;
		for(int j=lin[i];j!=0;j=bian[j].next)
		{
			cout<<"_--"<<bian[j].y<<':'<<bian[j].v<<endl;
		}
		cout<<endl;
	}*/
	cout<<sum<<endl;
	return 0;
}

强连通分量(dfn-low)

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
struct ss
{
	int y,next;
}e[100001];
int k=0,m,n,k1,top=0,num=0;
int lin[100001],flag[100001];
int q[100001],dfn[100001],low[100001],fa[100001];
void add(int x,int y)
{
	e[++k].next=lin[x];
	lin[x]=k;
	e[k].y=y;
}
int tarjan(int x)
{
	num++;
    dfn[x]=low[x]=num;
    q[++top]=x;//点入栈顶
    flag[x]=1;//标记该点以入栈
    for(int u=lin[x],v;u!=0;u=e[u].next)//dfs深度优先搜索
    {
        v=e[u].y;
        if(dfn[v]==0)//若该点并未标记dfn和low值，即从未进入栈
        {
            tarjan(v);//递归该点
            if(low[v]<low[x])low[x]=low[v];//通过该点low值更新自身low值
        }
        else 
			if(flag[v]!=0&&dfn[v]<low[x])//若该点以标记并且在栈里则更新当前所在点low
				low[x]=dfn[v];//不过为啥要和dfn比，不应该是和low比吗？
    }
	//cout<<x<<' '<<dfn[x]<<' '<<low[x]<<endl;
    if(dfn[x]==low[x])
    {
        k1++;
		cout<<"The"<<k1<<"th strongly connected component is:";
        while(q[top+1]!=x)
        {
			flag[q[top]]=0;
            cout<<q[top]<<' ';
            top--;
        }
		cout<<endl;
    }
	return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1,a1,a2;i<=m;i++)
    {
        cin>>a1>>a2;
        add(a1,a2);
    }
	k1=0;
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
			tarjan(i);
    }
	cout<<"There are "<<k1<<" strongly connected components in this Graph"<<endl;
	return 0;
}

求割点

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
struct ss
{
	int y,next,id;
}e[50000],e1[50000];
int lin[50000],lin1[50000],k=0,dfn[50000],low[50000],flag[50000];
int n,m,tt;
int q[50000],top=0;
void insert(int xx,int yy)
{
	e[++k].next=lin[xx];
	lin[xx]=k;
	e[k].y=yy;
}
void tarjan(int x,int fa)
{
	low[x]=dfn[x]=++tt;
	int son=0;
	for(int i=lin[x];i!=0;i=e[i].next)
	{	
		if(e[i].y==fa)
			continue;
		if(dfn[e[i].y]==0)
		{
			tarjan(e[i].y,x);
			if(low[e[i].y]>=dfn[x])
				son++;
		}
			low[x]=min(low[x],low[e[i].y]);
	}
	if(son>1||(son==1&&fa!=0))
		cout<<x<<endl;
}
int main()
{
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		insert(x,y);
		insert(y,x);
	}
	k=0;
	tarjan(1,0);
	return 0;
}

网络流

Edmond_Karp求最大流

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<algorithm>
#include<cstring>
#include<string.h>
#include<iostream>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
	int u,v,c;
	int next;
}edge[4000005];
int cnt=1;//边数
int head[40005];
void addedge(int u,int v,int c)
{
	edge[cnt].u=u; edge[cnt].v=v; edge[cnt].c=c; //正向边初始化为容量
	edge[cnt].next=head[u]; head[u]=cnt++;

	edge[cnt].u=v; edge[cnt].v=u; edge[cnt].c=0; //反向边容量初始化为0
	edge[cnt].next=head[v]; head[v]=cnt++;
}
bool visit[5005]; // 记录结点i是否已访问
int pre[5005]; //记录路径
int n,m,start,end; //源点，汇点
bool bfs()//寻找从源点到汇点的增广路，若找到返回true
{
    queue<int>q;
    memset(pre,-1,sizeof(pre));
    memset(visit,false,sizeof(visit));
	pre[start]=-1;
    visit[start]=true;
    q.push(start);
    while(q.empty()!=true)
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(edge[i].c>0&&visit[v]!=true)
            {
                pre[v]=i;
                visit[v]=true;
                if(v==end)
					return true;  //存在增广路
                q.push(v);
            }
        }
    }
    return false;
}
int Edmond_Karp()
{
	int sum=0;
	int delta;
    while(bfs())      //反复在源点到汇点间寻找增广路
	{
		delta=10000000000LL;
		int i=pre[end];
        while(i!=-1)
        {
            delta=min(delta,edge[i].c);   //路径上最小的容量为流量增量
            i=pre[edge[i].u];
        }
        i=pre[end];
        while(i!=-1)
        {
            // 路径上各边容量相应减少，反向边容量相应增加，总流量增加
            edge[i].c-=delta;   //增广路上的边减去使用的容量
            edge[i+1].c+=delta;  //同时相应的反向边增加残余容量
            i=pre[edge[i].u];
        }
        sum+=delta;
    }
    return sum;
}
int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	start=1,end=n;
    printf("%d\n",Edmond_Karp());
    return 0;
}

Dinic求最大流

Compared with the Edmond_Karp , the time complexity is better, because the depth arrays is used to reduce the meaningless path selection, and the cur arrays can also be used to optimize
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int Maxn=1e5+7;
struct ss
{
    int y,flow,Next;
}e[Maxn*2];//edge
int m,n,start,end,Link[Maxn],depth[Maxn],que[Maxn];
inline int read()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
inline void insert(int num,int xx,int yy,int ff)
{
    e[num].Next=Link[xx];
    Link[xx]=num;
    e[num].y=yy;
    e[num].flow=ff;
}
inline void init()
{
    n=read();m=read();start=read();end=read();
    for(int i=1,xx,yy,ff;i<=m;i++)
    {
        xx=read();yy=read();ff=read();
        insert(i*2,xx,yy,ff);//original edge
        insert(i*2+1,yy,xx,0);//opposite edge
    }
}
inline bool bfs()
{
    int head=1,tail=1,xx,yy;
    memset(depth,0,sizeof(depth));
    depth[start]=1;que[1]=start;
    for(;head<=tail;head++)
    {
        xx=que[head];
        for(int i=Link[xx];i;i=e[i].Next)
            if(e[i].flow&&!depth[yy=e[i].y])
            {
                depth[yy]=depth[xx]+1;
                que[++tail]=yy;
            }
    }
    return depth[end];
}
inline int dfs(int xx,int Nowflow)//Use DFS to search the flow which we can add.
{
    if(xx==end) return Nowflow;
    int yy,Addflow,ataf=0;//ataf=able to add flow;
    for(int i=Link[xx];i&&ataf< Nowflow;i=e[i].Next)
        if (e[i].flow&&depth[yy=e[i].y]==depth[xx]+1)//To make sure we can add this flow.&&It must be in more depth.
        {
            Addflow=dfs(yy,min(Nowflow-ataf,e[i].flow));
            e[i].flow-=Addflow;
            e[i^1].flow+=Addflow;
            ataf+=Addflow;
        }
    if(ataf==0) depth[xx]=0;//If we cannot add flow on this point,we will never use it.
    return ataf;
}
int Dinic()
{
    int ans=0;
    for(;bfs();)//Every times,we use bfs to find if we can add some flow
        for(int x;(x=dfs(start,INF));)ans+=x;//When we find that it is passible, use dfs to add the flow.
    printf("%d\n",ans);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    init();
    Dinic();
    return 0;
}

当前弧优化的Dinic

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int Maxn=1e5+7;
struct ss
{
    int y,flow,Next;
}e[Maxn*2];
int m,n,start,end,Link[Maxn],depth[Maxn],que[Maxn],cur[Maxn];
inline int read()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
inline void insert(int num,int xx,int yy,int ff)
{
    e[num].Next=Link[xx];
    Link[xx]=num;
    e[num].y=yy;
    e[num].flow=ff;
}
inline void init()
{
    n=read();m=read();start=read();end=read();
    for(int i=1,xx,yy,ff;i<=m;i++)
    {
        xx=read();yy=read();ff=read();
        insert(i*2,xx,yy,ff);
        insert(i*2+1,yy,xx,0);
    }
}
inline bool bfs()
{
    int head=1,tail=1,xx,yy;
    memset(depth,0,sizeof(depth));
    depth[start]=1;que[1]=start;
    for(;head<=tail;head++)
    {
        xx=que[head];
        for(int i=Link[xx];i;i=e[i].Next)
            if(e[i].flow&&!depth[yy=e[i].y])
            {
                depth[yy]=depth[xx]+1;
                que[++tail]=yy;
            }
    }
    return depth[end];
}
inline int dfs(int xx,int Nowflow)
{
    if(xx==end) return Nowflow;
    int yy,Addflow,ataf=0;
    for(int i=cur[xx];i&&ataf< Nowflow;i=e[i].Next)
    {
        cur[xx]=i;//Mark the last pass point and search directly from it next time。
        if (e[i].flow&&depth[yy=e[i].y]==depth[xx]+1)
        {
            Addflow=dfs(yy,min(Nowflow-ataf,e[i].flow));
            e[i].flow-=Addflow;
            e[i^1].flow+=Addflow;
            ataf+=Addflow;
        }
    }
    if(ataf==0) depth[xx]=0;
    return ataf;
}
int Dinic()
{
    int ans=0;
    for(;bfs();)
    {
        memcpy(cur,Link,sizeof(Link));//Change the cur arrayy every times.
        for(int x;(x=dfs(start,INF));)
            ans+=x;
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    init();
    Dinic();
    return 0;
}

最小费用最大流(EK+SPFA)

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=100010;
long long vis[maxn],dis[maxn],maxflow=0,mincost=0;
int n,m,s,t;
int pre[maxm];//pre[] is an arrey record the last point of the path which is possible.
int last[maxm];//last[] is an arrey record the edge to the last point of the path.
int STNF[maxn];//STNF[] is the flow which from start point to the point right now.
struct ss
{
	int y,next,flow,v;
}e[maxm << 1];
int Link[maxn],edgenum; 
int q[maxm<< 1],head,tail;
//Attation!the size of the que is not direct,so we need to define it in a large size.
inline void insert(int xx,int yy,int ff,int vv)
{
	e[++edgenum].next=Link[xx];
	e[edgenum].y=yy;
	e[edgenum].flow=ff;
	e[edgenum].v=vv;
	Link[xx]=edgenum;
}
inline void Init()
{
    memset(Link,-1,sizeof(Link)); edgenum=1;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (int i=1,xx,yy,vv,ff;i<=m;i++)
	{
		scanf("%d%d%d%d",&xx,&yy,&ff,&vv);
		insert(xx,yy,ff,vv);
        insert(yy,xx,0,-vv);
	}
}
inline bool spfa(int s,int t)
{
	memset(dis,0x7f,sizeof(dis));
	memset(STNF,0x7f,sizeof(STNF));
	memset(vis,0,sizeof(vis));
    head=0;tail=0;
	q[++tail]=s; vis[s]=1; dis[s]=0; pre[t]=-1;
	
	while(head<tail)
	{
		int now=q[++head];
		vis[now]=0;
		for (int i=Link[now];i!=-1;i=e[i].next)
		{
			if (e[i].flow>0 && dis[e[i].y]>dis[now]+e[i].v) 
			{
				dis[e[i].y]=dis[now]+e[i].v;
				pre[e[i].y]=now;last[e[i].y]=i;//recording the path.
				STNF[e[i].y]=min(STNF[now],e[i].flow);//renew the flow at this point.
				if(!vis[e[i].y])
				{
					vis[e[i].y]=1;
					q[++tail]=e[i].y;
				}
			}
		}
	}
	return pre[t]!=-1;
}

inline void MCMF()
{
	while(spfa(s,t))
	{
        //for(int i=1;i<=n;i++)cout<<dis[i]<<' ';cout<<endl;
		int now=t;
		maxflow+=STNF[t];
		mincost+=STNF[t]*dis[t];
        //cout<<STNF[t]<<' '<<dis[t]<<endl;
		while(now!=s)
		{
            //cout<<now<<'-';
			e[last[now]].flow-=STNF[t];
			e[last[now]^1].flow+=STNF[t];
            now=pre[now];
		}//cout<<endl;
	}
	printf("%d %d",maxflow,mincost);
}

int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    //int kl= clock();
    Init();
	MCMF();
    //cout<<clock()-kl<<endl;
	return 0;
}

Kruskal重构树

通常用来求路径上极值问题

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+5,M=6e4+5,logN=15+1;
int n,m,q,kl,fa[N],Link[N],val[N],yy[M],Next[M],f[N][logN],dep[N];
struct ss
{
    int u,v,w;
    bool operator < (const ss &rhs) const {
        return w<rhs.w;
    }
}e[M];
void add(int u,int v){yy[++kl]=v,Next[kl]=Link[u],Link[u]=kl;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kruskal()
{
    sort(e+1,e+m+1);
    int lim=n+n;
    for(int i=1;i<=lim;++i)fa[i]=i;
    for(int idx=n,i=1;i<=m;++i)
    {
      int fu=find(e[i].u),fv=find(e[i].v);
      if(fu==fv) continue;
      fa[fu]=fa[fv]=++idx,val[idx]=e[i].w;
      add(idx,fu),add(idx,fv);
      if(idx==lim-1) break;
    }
}
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=1;(1<<i)<=dep[u];++i)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=Link[u];i;i=Next[i])if(yy[i]!=fa)dfs(yy[i],u);
}
int lca(int u,int v)
{
    if(dep[u]>dep[v]) u^=v^=u^=v;
    for(int i=15;~i;--i)if(dep[f[v][i]]>=dep[u]) v=f[v][i];
    if(u==v) return u;
    for(int i=15;~i;--i)if(f[u][i]^f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;++i)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    kruskal();//建生成树
    dfs(2*n-1,0);//预处理递增
    while(q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",val[lca(u,v)]);
    }
    return 0;
}

堆优化Dijkstra

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<algorithm>
#include<cstring>
#include<iostream>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<vector>
#include<cstdio>
#include<ctime>
#include<cmath>
#include <cstdlib>
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
struct ss
{
	int x,y,v,next;
}e[500010];
int n,m,s;
int Link[100010],k=0;
long long dis[100010];
inline void insert(int xx,int yy,int vv)
{
	e[++k].x=xx;e[k].y=yy;e[k].v=vv;
	e[k].next=Link[xx];
	Link[xx]=k;
}
struct node {
    int u,d;
    bool operator <(const node& rhs) const{return d>rhs.d;}
};
priority_queue<node>Q; 
inline void dj(int st)
{
    for (int i=0;i<=n;i++) dis[i]=100000000000ll;
	dis[st]=0;
	node minpoint;
	minpoint.u=st;minpoint.d=0;
    Q.push(minpoint);
	while(Q.size())
	{
        minpoint=Q.top();Q.pop();
        int u=minpoint.u,d=minpoint.d;
		if (dis[u]!=d) continue ;
		//cout<<u<<' '<<d<<endl;
        //if (d!=dis[u]) continue;
		for(int j=Link[u];j;j=e[j].next)//用最近的点来更新其他点的最近距离
		{//保证了前一步找最近的点时找到的就是该点的最短路
			if(dis[e[j].y]>d+e[j].v)
			{
				dis[e[j].y]=d+e[j].v;
                Q.push((node){e[j].y,dis[e[j].y]});
			}
		}
        //minpoint=Q.top();Q.pop();
        //u=minpoint.u,d=minpoint.d;
		//cout<<u<<' '<<d<<endl;
	}

}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	//int jk=clock();
	n=read();m=read();s=read();
	for(int i=1,xx,yy,vv;i<=m;i++)
	{
		xx=read();yy=read();vv=read();
		insert(xx,yy,vv);
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<':'<<endl;
		for(int j=Link[i];j;j=e[j].next)
		{
			cout<<"  -"<<e[j].y<<':'<<e[j].v<<endl;
		}
	}*/
	dj(s);
	//cout<<n<<endl;
	for (int i=1;i<=n;i++) printf("%d ",dis[i]);
	//cout<<clock()-jk<<endl;
	return 0;
}
/*
dj的原理在于从起始点(点一)到目标点(点二)的最短路径上，
每一点(点三)都是最短的路径。由反证法得知，若该路径不是最短的路径，
呢么必有从起始点(点一)到中间某一点(点三)的另一条路径是起始点(点一)到目标点(点二)的最短路径的组成部分
故从起始点到目标点的最短路径可由(起始点到中间点的最短路和中间点到目标点路径长度求和后最小值)求得
*/

字符串

kmp

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
char s1[1000001],s2[1000001];
int Next[1000001],ii=0,jj=0;
int Next1[1000001];
inline void FindNext()
{
    jj=0;//jj在Next数组建立时的含义为S1前缀子串中前缀与后缀相同的长度
    for(ii=1;ii<n;ii++)//遍历s1的下标，从1也就是第二位开始
    {
        for(;jj!=0&&s1[ii]!=s1[jj];)jj=Next[jj]; //s1[jj]为为S1前缀子串中已匹配前缀后的一个字母
        if(s1[ii]==s1[jj])jj++;//同上，若相同则jj即长度++;
        Next[ii+1]=jj;//Next[ii+1]指的是s1的第ii位(下标从0开始，下标是ii对应的就是第ii+1位)前缀子串中前缀与后缀相同的长度
    }
}
inline void Find_string()
{

	jj=0;  //jj在两字符串匹配时的含义是已经匹配的长度，未匹配时长度为0
	for(ii=0;ii<m;ii++)
	{
        for(;(jj>0)&&(s1[jj]!=s2[ii]);)jj=Next[jj];//s1[jj]为为S1前缀子串中 已匹配前缀 后的第一个字母
		if(s1[jj]==s2[ii])jj++;//若以匹配前缀后字母相同则长度++
		if(jj==n) //找到匹配，当然可以继续找下一个匹配
		{
			cout<<ii-jj+2<<endl;//注意，ii为下标，即从零开始，故找到的s2中的一个s1字串的起始位置是ii-jj+2
			jj=Next[jj];//最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配
		}
    }   
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
	memset(Next,0,sizeof(Next));
    scanf("%s%s",s2,s1);//注意，本代码中字符数组下标均为从0开始
    n=strlen(s1);
    m=strlen(s2);
    FindNext();
    Find_string();
    for(int i=1;i<=n;i++)cout<<Next[i]<<' ';//输出Next数组
    cout<<endl;
    return 0;
}

tiretree

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<ctime> 
#include<vector>
#include<queue>
using namespace std;
struct node
{
    char ch;        	 //本节点的值
    bool endflag; 	//是否是某个单词的最后一个字符
    int link[26]; 		//26个分叉
}tree[600100];
int len=0;
void add(int k,int node,string s)  //k是s的第k个字符，node为当前节点。
{      
    int  chindex=s[k]-'a';  //字符的编号
    if (tree[node].link[chindex]==0)   //新开节点
	{
		tree[node].link[chindex]=++len;    		
		tree[len].ch=s[k]; 
		tree[len].endflag=false;
	}
	int nexnode=tree[node].link[chindex];  //下一个节点的下标
    if (k==(int)s.size()-1)
    {
        tree[nexnode].endflag=true;
        return;
    }
    add(k+1,nexnode,s);    
}
bool find(int k,int node,string s)
//k是要查找字符串s的第k个元素
{
    int chindex=s[k]-'a';
    if (tree[node].link[chindex]==0)  return false;
    int nextnode=tree[node].link[chindex];
    if(k==(s.size()-1)) //如果k是最后一个字符
       if(tree[nextnode].endflag)  
		   return true;
        else                                    
			return false;
    return find(k+1,nextnode,s);
}
int main()
{
	string s1,s2;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s1;
		add(0,0,s1);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s2;
		if(find(0,0,s2)==true)
			cout<<"True"<<endl;
		else
			cout<<"False"<<endl;
	}
    return 0;
}

AC自动机

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<ctime> 
#include<vector>
#include<queue>
using namespace std;
struct node
{
    char ch;        	 //本节点的值
    int endflag; 	//是否是某个单词的最后一个字符
    int link[26]; 		//26个分叉
    int fa;          //记录节点的父亲
}tree[1000010];
int len=0,sum=0,s1size,s2size,panduan=0;
char s1[1000010],s2[1000010];
int Fail[10000010];//记录第i个点匹配失败后跳到的节点
int q[1000010],head,tail;
inline void add(int k,int node)  //k是s的第k个字符，node为当前节点（是字符串下标为k的字母节点的父节点）。
{      
    int  chindex=s1[k]-'a';  //字符的编号
    if (tree[node].link[chindex]==0)   //新开节点
	{
		tree[node].link[chindex]=++len;    		
		tree[len].ch=s1[k]; 
		tree[len].endflag=0;
		tree[len].fa=node;
	}
    if (k==s1size-1)//若已经将s1添加完，使其最后一个字母节点endflag++；
    {
        tree[tree[node].link[chindex]].endflag++;
        return;
    }   
    add(k+1,tree[node].link[chindex]);    //跳到下一个节点
}
inline void makeFail(int node)//y用BFS进行Fail指针的建立，因为Fail指针永远向上，故用BFS可确保建立Fail时指向的节点已经完整的建立了Fail路径
{    
    head=tail=1;
    q[tail]=node;
    for(int i=head,Nowch,FF;i<=tail;i++)
    {
        for(int j=0;j<26;j++)if(tree[q[i]].link[j]!=0)q[++tail]=tree[q[i]].link[j];//将存在的子节点都加入队列
        Nowch=tree[q[i]].ch-'a';
        for(FF=Fail[tree[q[i]].fa];tree[FF].link[Nowch]==0&&FF!=0;FF=Fail[FF]);//循环，每次跳到父亲的Fail指针指向的节点，判断节点是否有该字符的子节点。持续知道找到这么个节点或是到达根节点
        if(tree[q[i]].fa==0)Fail[q[i]]=0;//若FF为0节点即第一层节点，呢么Fail指针直指0节点
        else Fail[q[i]]=tree[FF].link[Nowch];//将该点的失败指针指向父节点Fail最终停下来的子节点，即最终找到的节点
    }
}
inline void dfs(int node)//打表，请自行忽略
{
    cout<< node<<"  是否end  "<<tree[node].endflag<<endl;
    for(int i=0;i<26;i++)
        if(tree[node].link[i]!=0)
            cout<<"   "<<(char)(i+'a')<<':'<<tree[node].link[i]<<endl;
    for(int i=0;i<26;i++)
        if(tree[node].link[i]!=0)
            dfs(tree[node].link[i]);
}
int main()
{
    memset(Fail,0,sizeof(Fail));
    memset(tree,0,sizeof(tree));
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);eeeeee
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s1);
        s1size=strlen(s1);
		add(0,0);
	}
    makeFail(0);
    //dfs(0);
    scanf("%s",s2);
    s2size=strlen(s2);
   
	//find(0,0);
    for(int k=0,node=0,chnode,chindex;k<s2size;k++)//查找，k为s2的下标，node为当前节点，chnode为当前节点的与s2此时下标所表示字符相同的子节点，相当于s2中的字符实际上匹配的是子节点而不是node
    {
        chindex=s2[k]-'a';
        chnode=tree[node].link[chindex];
        for(;chnode==0&&node!=0;node=Fail[node],chnode=tree[node].link[chindex]);//子节点为0表示当前的node并没有相对应的子节点，故需通过Fail指针进入下一节点。node为0时表明已经到达根节点无法再通过Fail指针跳跃，chnode不为0表示当前节点有一子节点和s2的当前字符匹配，这两种情况退出Fail跳跃
        if(tree[chnode].endflag!=0)sum+=tree[chnode].endflag,tree[chnode].endflag=0;//当chnode为终止节点时计数器增加，Fail跳跃循环的第一种退出循环的方式chnode的endflag必为0故不会妨碍
        node=chnode;//通过Fail跳跃此时的chnode必与s2此时下标所表示字符相同或者为0(为0即重新开始下一个字符)，由当前节点进入chnode，进行下一次操作
        //cout<<node<<' '<<chindex<<' '<<chnode<<' '<<tree[chnode].ch<<'-'<<tree[chnode].endflag<<"   dsf"<<sum<<endl;
    }
    cout<<sum<<endl;
    return 0;

后缀树

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
string s1;
struct ss
{
	int note;
	int ch1;
	int lengh;
}active;
struct tt
{
	int ch[30];
	int begin;
	int end;
	int lianjie;
}tree[500010];
int kl=0;
int last=-1;
int fenlie(int k)
{
	if(active.lengh==0)
		return 0;
	tree[tree[active.note].ch[active.ch1]].ch[s1[active.lengh+tree[tree[active.note].ch[active.ch1]].begin]-'a'+1]=++kl;
	tree[tree[active.note].ch[active.ch1]].end=active.lengh+tree[tree[active.note].ch[active.ch1]].begin-1;
	tree[kl].begin=active.lengh+tree[tree[active.note].ch[active.ch1]].begin;
	tree[kl].end=-1;
	//先将原边分为两条
	tree[tree[active.note].ch[active.ch1]].ch[s1[k]-'a'+1]=++kl;
	tree[kl].begin=k;
	tree[kl].end=-1;
	//创建新加入点的新边
	if(active.note==0)
	{
		active.lengh--;
		if(active.lengh==0)
			return 0;
		int jk1=s1[tree[tree[active.note].ch[active.ch1]].begin+1]-'a'+1;//下一个点的字符
		tree[tree[active.note].ch[active.ch1]].lianjie=tree[active.note].ch[jk1];//后缀链接
		active.ch1=jk1;
		fenlie(k);
	}
	else
	{
		active.note=tree[active.note].lianjie;
		fenlie(k);
	}
}
int built(int k)
{
	int jk=s1[k]-'a'+1;//要插入的点
	if(active.lengh==0)//没有活动点时
	{
		if(tree[active.note].ch[jk]==0)//没有记录就添新边
		{
			tree[active.note].ch[jk]=++kl;
			tree[kl].begin=k;
			tree[kl].end=-1;
		}
		else//有记录加入活动点
		{
			active.ch1=jk;
			active.lengh++;
		}
	}
	else
	{
		//tree[active.note].ch[active.ch1]是活动节点的编号
		int yu=k-tree[tree[active.note].ch[active.ch1]].begin;//yu是这个点现在所记录的长度
		int yu1=tree[tree[active.note].ch[active.ch1]].begin+active.lengh;//yu1是这个点的第lengh位
		if(s1[yu1]==s1[k])
		{
			active.lengh++;
		}
		else
		{
			last=-1;
			fenlie(k);
		}
		
	}
	return 0;
}
int main()
{
	memset(tree,0,sizeof(tree));
	active.note=active.ch1=active.lengh=0;
	cin>>s1;
	built(0);
	return 0;
}

后缀数组

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
char ch[MAXN], All[MAXN];
int SA[MAXN], rank[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m; 
char str[MAXN];
//rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
//tax[i] 计数排序辅助数组; tp[i] rank的辅助数组(计数排序中的第二关键字),与SA意义一样。
//a为原串
void RSort()
{
    //rank第一关键字,tp第二关键字。
    for(int i=0;i<=m;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[rank[tp[i]]]++;
    for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--)SA[tax[rank[tp[i]]]--]=tp[i]; //确保满足第一关键字的同时，再满足第二关键字的要求
} //计数排序,把新的二元组排序。

int cmp(int *f, int x, int y, int w) {return f[x]==f[y]&&f[x+w]==f[y+w];} 
//通过二元组两个下标的比较，确定两个子串是否相同

void Suffix() {
    //SA
    for(int i=1;i<=n;i++)rank[i]=a[i],tp[i]=i;
    m=127,RSort(); //一开始是以单个字符为单位，所以(m = 127)

    for(int w=1,p=1,i;p<n;w+=w,m=p)//把子串长度翻倍,更新rank
	{
        //w 当前一个子串的长度; m 当前离散后的排名种类数
        //当前的tp(第二关键字)可直接由上一次的SA的得到
        for(p=0,i=n-w+1;i<=n;i++)tp[++p]=i; //长度越界,第二关键字为0
        for(i=1;i<=n;i++)
			if(SA[i]>w)
				tp[++p]=SA[i]-w;
        //更新SA值,并用tp暂时存下上一轮的rank(用于cmp比较)
        RSort(); 
		for(int i=0;i<m;i++)
		{
			int t=rank[i];
			rank[i]=tp[i];
			tp[i]=t;
		}
		rank[SA[1]]=1;
		p=1;
        //用已经完成的SA来更新与它互逆的rank,并离散rank
        for(i=2;i<=n;i++)rank[SA[i]]=cmp(tp,SA[i],SA[i-1],w)?p:++p;
    }
    //离散：把相等的字符串的rank设为相同。
    //LCP
    int j, k=0;
	for(int i=1;i<=n;Height[rank[i++]]=k) 
    {
		//for(k=(k!=0)?k-1:k,j=sa[rank[i]-1];a[i+k]==a[j+k];++k);
        for(k=(k!=0)?k-1:k;;)
		{
			/*if(k!=0)
				k=k-1;
			else
				k=k;*/
			j=SA[rank[i]-1];
			if(a[i+k]==a[j+k])
				++k;
			else
				break;
		}
	}
    //这个知道原理后就比较好理解程序
}


int main()
{
    scanf("%s",str);
    n=strlen(str);
    for(int i=0;i<n;i++)a[i+1]=str[i];
    Suffix();
	for(int i=2;i<=n;i++)
		cout<<Height[i]<<endl;
    return 0;  
}

后缀自动机(咕)

1
啊这，怎么这个也咕了啊

字符串hash

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstring>
using namespace std;
const int mod=2323237;
int a[2323238][9];//114MB
string s11[10001];
inline int find(int t)
{
	long long sum=0,kl=1;
	for(int j=0;j<s11[t].size();j++)
	{
		int yu=(int)(s11[t][j]-'1'+1);
		sum+=yu*kl;
		kl*=26;
		kl%=mod;
		sum%=mod;
	}
	//cout<<sum<<' '<<t<<endl;
	for(int i=1;i<=a[sum][0];i++)
	{
		if(s11[a[sum][i]]==s11[t])
			return 1;
	}
	a[sum][++a[sum][0]]=t;
	//cout<<sum<<' '<<a[sum][0]<<' '<<t<<endl;
	return 0;
}
int main()
{
	//freopen("a1.in","r",stdin);
	//freopen("a1.out","w",stdout);
	memset(a,0,sizeof(a));
	int n,sum=0;
	scanf("%d\n",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>s11[i];
		if(find(i)==0)
			sum++;
	}
	cout<<sum<<endl;
	return 0;
}

数论

数论的总结更在了这里

计算几何

计算几何的总结在这里

其他

LCA

ST+DFS在线

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>//这个库必须加
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
struct edge 
{
    int y,v,next;
}e[1000010];
int len=0,lin[1000010];
int a[1000110],aa=0,dp[1000100],kkl[1000010],r[1000010],kl[19],n,m,s,f[1000010][19],e1[1000010][19],lenk[1001000];
inline void dfs(int k,int dd)
{
    a[++aa]=k;
    dp[aa]=dd;
	if(r[k]==0)
		r[k]=aa;
    for(int i=lin[k];i!=0;i=e[i].next)
    {
		if(kkl[e[i].y]==0)
		{
			kkl[e[i].y]=1;
			dfs(e[i].y,dd+1);
			a[++aa]=k;
			dp[aa]=dd;
		}
    }
    return ;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    cin>>n>>m;
	//int k=clock();
    for(int i=1,x,y;i<=n-1;++i)
    {
       x=read();
	   y=read();
        {
            e[++len].next=lin[x];
            lin[x]=len;
            e[len].y=y;
        }
		{
            e[++len].next=lin[y];
            lin[y]=len;
            e[len].y=x;
        }
    }
	
			kkl[1]=1;
    dfs(1,0);
    //cout<<aa<<endl;
    /*for(int i=1;i<=aa;i++)
    {
        cout<<a[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=aa;i++)
    {
        cout<<dp[i]<<' ';
    }
    cout<<endl;
    
    for(int i=1;i<=n;i++)
    {
        cout<<r[i]<<' ';
    }
    cout<<endl;*/
    int kl1=0;
    for(int i=1;i<=aa;++i)
    {
        f[i-1][1]=min(dp[i-1],dp[i]);
        if(dp[i-1]<=dp[i])
            e1[i-1][1]=i-1;
        else
            e1[i-1][1]=i;
    }
    f[aa][1]=dp[aa];
	e1[aa][1]=aa;
    for(int yu=2;yu<=aa;yu<<=1)
        kl[++kl1]=yu;
    for(int j=2;j<=kl1;++j)
        for(int i=1;i<=aa;++i)
        {
            if(f[i][j-1]<=f[i+kl[j-1]][j-1])
            {
                e1[i][j]=e1[i][j-1];
                f[i][j]=f[i][j-1];
            }
            else
            {
                e1[i][j]=e1[i+kl[j-1]][j-1];
                f[i][j]=f[i+kl[j-1]][j-1];
                
            }
        }
    for(int i=1,j=1,z;i<=aa;++i)
    {
        if(i>kl[j]<<1)
            j++;
        lenk[i]=j;
    }
    for(int i=1,x,y,yu;i<=m;++i)//输入区间
    {
       x=read();
	   y=read();
	   if(x==y)
		{   cout<<x<<endl;
	   continue;}
        x=r[x];
        y=r[y];
        int yu1=max(x,y);
        x=min(x,y);
        y=yu1;
        int lenn=y-x+1;
        if(f[x][lenk[lenn]]<=f[y-kl[lenk[lenn]]+1][lenk[lenn]])
            yu=e1[x][lenk[lenn]];
        else
            yu=e1[y-kl[lenk[lenn]]+1][lenk[lenn]];
        //cout<<f[x][lenk[lenn]]<<' '<<x<<' '<<lenk[lenn]<<endl;
        //cout<<f[y-kl[lenk[lenn]]][lenk[lenn]+1]<<' '<<y-kl[lenk[lenn]]<<' '<<lenk[lenn]<<endl;
        cout<<a[yu]<<endl;
    }
	//cout<<clock()-k<<endl;
    return 0;
}

倍增 离线

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<ctime>
using namespace std;
struct ss
{
	int y,next;
}e[1000010];
int lin[1000010],kl,n,m,kkk[1000010];
inline void insert(int xx,int yy)
{
	e[++kl].next=lin[xx];
	lin[xx]=kl;
	e[kl].y=yy;
}
int dep[1000010],fa[1000010];
int ff[1000010][40];
inline void dfs1(int now,int dd)
{
	//cout<<fa[now]<<' '<<now<<endl;
	dep[now]=dd;
	//cout<<now<<':'<<endl;
	for(int j=1;(1<<j)<=dep[now];j++)
	{
		ff[now][j]=ff[ff[now][j-1]][j-1];
		//cout<<"     "<<j<<':'<<ff[now][j]<<endl;
	}
	for(int i=lin[now];i!=0;i=e[i].next)
	{
		if(kkk[e[i].y]==0)
		{
			kkk[e[i].y]=1;
			ff[e[i].y][0]=fa[e[i].y]=now;
			dfs1(e[i].y,dd+1);
		}
	}
}
int LCA(int u,int v)  
{  
    if(dep[u]<dep[v])swap(u,v);
    int delta=dep[u]-dep[v];
    for(int x=30;x>=0;x--)  
        if((1<<x)&delta)
            u=ff[u][x];  
    if(u==v)
		return u;  
    for(int x=30;x>=0;x--)
        if(ff[u][x]!=ff[v][x])
        {  
            u=ff[u][x];  
            v=ff[v][x];
        }  
    return ff[u][0];
} 
int root;
int main()
{
	//freopen("subset.in","r",stdin);
	//freopen("subset.out","w",stdout);
	//    freopen("a.in","r",stdin);
	//freopen("add2.out","w",stdout);
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i<n;i++)
	{
		int xx,yy;
		scanf("%d%d",&xx,&yy);
		insert(xx,yy);
		insert(yy,xx);
	}
	kkk[root]=1;
	ff[root][0]=fa[root]=root;
	
	dfs1(root,1);
	for(int i=1;i<=m;i++)
	{
		int xx,yy,vv;
		scanf("%d%d",&xx,&yy);
		vv=LCA(xx,yy);
		printf("%d\n",vv);
	}
	return 0;
}

并查集

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int fa[5000],k,a1,a2;
int find(int kk)
{
	if(fa[kk]==kk)
		return kk;
	return fa[kk]=find(fa[kk]);
}
void add(int xx,int yy)
{
	int faxx=find(xx);
	int fayy=find(yy);
	fa[faxx]=fayy;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>k>>a1>>a2;
		if(k==1)
			add(a1,a2);
		if(k==2)
		{
			if(find(a1)==find(a2))
				cout<<"Yes"<<endl;
			else
				cout<<"Nop"<<endl;
		}
	}	
	return 0;
}

RMQ求区间最值

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>//RMQ求区间最值
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
int n,m,a[100020];
int f[100020][20];//f[i][j]表示从第i位开始往后2^j位的最值
int kl[20];//kl[i]指的是2^i
int kl1[100020];//kl1[i]表示i小于等于2的几次方
int main()
{
	memset(a,10,sizeof(a));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i][0]=a[i];
	}
	kl[0]=1;
	kl1[1]=0;
	for(int i=1;i<=20;i++)
	{
		kl[i]=kl[i-1]*2;
		if(kl[i]>=n)
			break;
		kl1[kl[i]]=kl1[kl[i-1]]+1;
	}
	for(int k=1;kl[k]<=n;k++)//循环k保证存在2^k小于n
		for(int i=1;i<=n;i++)//从第一位循环到第n位（其实可以优化下循环到n-kl[k])
			f[i][k]=min(f[i][k-1],f[i+kl[k-1]][k-1]);//递推式，第i位往后2^k个数的最值通过 {第i位往后2^(k-1)个数的最值} 和 {第（i+2^(k-1)）位往后2^(k-1)个数的最值}  求出
	for(int i=1;i<=n;i++)
	{
		if(kl1[i]==0)
			kl1[i]=kl1[i-1];//补完kl1
	}
	for(int i=1,x,y,z;i<=m;i++)
	{
		cin>>x>>y;
		z=max(x,y);x=min(x,y);y=z;//令x为左区间，y为右区间
		int lenn=y-x+1;//长度
		int yu=min(f[x][kl1[lenn/2]+1],f[y-lenn/2][kl1[lenn/2]+1]);//2^(kl1[lenn/2]+1)<=lenn
		cout<<yu<<endl;
	}
	return 0;
}

快捷离散化

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int p[maxn], a[maxn],D,n;
int main() 
{
	//freopen("a.in","r",stdin);
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i],a[i]=p[i];
    sort(p+1,p+n+1);D=unique(p+1,p+n+1)-p-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(p+1,p+D+1,a[i])-p;
	for(int i=1;i<=n;i++)cout<<a[i]<<'\n';//a[i]为第i个数的名次,名次为去重过后的
    return 0;
}

算法 模板
acm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！