动态规划
1.背包问题
(1)01背包
voidZeroOnepack(int F[],int C[],int W[]){ FOR(i,1,n)DFR(v,V,C[i])F[v]=max(F[v],F[v-C[i]]+W[i]);}//初始化时//若背包不一定装满F全初始化为0//若装满 F[0]=0 其他为-inf
voidCompletePack(int F[],int C[],int W[]){ FOR(i,1,n)FOR(v,C[i],V){F[v]=max(F[v],F[v-C[i]]+W[i]);}}
voidMultiplePack(int F[],int C[],int W[],int M[]){if(C[i]*M[i]>=V){CompletePack(F,C,W);return;}k=1;whlie(k<M[i]){ZeroOnePack(k*C[i],k*W[i]);M[i]=M[i]-k;k<<=1;ZeroOnePack(C[i]*M[i],W{i]*M[i])}}
FOR(i,1,n){if(第i件物品属于01背包)ZeroOnePack(F,C[i],W[i]);elseif(第i件物品属于全然背包)CompletePack(F,C[i],W[i]);elseif(第i件物品属于多重背包)MultiplePack(F,C[i],W[i],N[i]);}
2.LIS
int n;int a[Maxn];omt dp[Maxn];int LIS(){int res=0;FOR(i,0,n-1){ dp[i]=1;FOR(j,0,i-1){if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);}res=max(res,dp[i]);}return res;}
#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>usingnamespace std;constint maxn=1010;int dp[maxn][maxn];char s1[maxn],s2[maxn];int main(){int i,j,len1,len2;while(~scanf("%s%s",s1+1,s2+1)){len1=strlen(s1+1);len2=strlen(s2+1);memset(dp[0],0,sizeof dp[0]);for(i=1;i<=len1;i++){for(j=1;j<=len2;j++){if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}printf("%d\n",dp[len1][len2]);}return0;}
#include<iostream>usingnamespace std;#define N 1010int n,m,x,y;int a[N][N];int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d%d%d",&n,&m,&x,&y);int i,j;int ans=-1;memset(a,0,sizeof(a));for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&a[i][j]);a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];if(i>=x && j>=y){int tmp=a[i][j]-a[i-x][j]-a[i][j-y]+a[i-x][j-y];if(tmp>ans)ans=tmp;}}}printf("%d\n",ans);}return0;}
贪心
搜索
void DFS(int step){推断边界尝试每一种可能FOR(i,1,n){继续下一步DFS(step++);}返回}
图论
邻接表
//初始化first数组下标1-n的值为-1,表示1-n顶点临时都没有边int u[Maxn+1],v[maxn+1],w[Maxn+1],first[Maxn],next[Maxn];FOR(i,1,n)first[i]=-1;FOR(i,1,m){scanf(“%d%d%d”,&u[i],&v[i],&w[i]);next[i]=first[u[i]];first[u[i]]=i;}//遍历每一个顶点的边FOR(i,1,n){ k=first[1];while(k!=-1){printf("%d %d %d\n",u[k],v[k],w[k]);k=next[k];}}//时间复杂度O(M)//空间复杂度O(M)
1.Floyd算法
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
步骤:
(1)将全部顶点分为两部分:已知最短路径的顶点集合P和未知最短路径的顶点集合Q。最開始,已知最短路径的顶点集合P中仅仅有源点一个顶点。我们这里用一个book数组来记录哪些点在集合P里。
(2)设置源点s到自己的最短路径为0即dis[i]=0。若存在有源点能直接到达的顶点i,则把dis[i]设为e[s][i]。同一时候把全部其他(源点不能直接到达的)顶点的最短路径设为INF
(3)在集合Q的全部顶点中选择一个离源点近期的顶点u(即dis[u]最小)加入到集合P。并考察全部以点u为起点的边,对每一条边进行松弛操作。比如存在一条从u到v的边,那么能够通过将边加入到尾部来拓展一条从s到v的路径,这条路径的长度是dis[u]+e[u][v]。
假设这个值比眼下已知的dis[v]的值要小,我们能够用新值来替代当前dix[v]的值。
(4)反复第(3)步,假设集合Q为空,算法结束。终于dis数组中的值就是源点到全部顶点的最短路径
voidDijkstra(){ FOR(i,1,n-1){ min=inf;FOR(j,1,n){if(!book[j]&& dis[j]<min){min=dis[j];u=j;}}book[u]=1;FOR(v,1,n){if(e[u][v]<inf)dis[v]=min(dis[v],dis[u]+e[u][v]);}}}//时间复杂度O(n2) 能够用堆优化近期顶点 对于稀疏图用邻接表存 复杂度O((m+n)logn)
FOR(k,1,n-1)FOR(i,1,m)dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);//是否能通过u[i]->v[i]这条边使得源点到v[i]号顶点的距离变短
割点和割边(Tarjan算法)
朴素思想:依次删除顶点推断图是否连通,DFS或BFS,时间复杂度O(N(N+M))
推断:若k是割点,则深度优先遍历到k时剩下的没有被訪问过的点中至少会有一个点在不经过k点的情况下,无法回到已訪问的节点.即一个连通图被k切割成多个不连通的子图.
关键:怎样检測顶点v在不经过父顶点u的情况下是否能回到祖先
方法:对v再进行一次DFS,不能经过顶点u,看是否能回到祖先
二分图最大匹配
思路:
1.匈牙利算法
(1)首先从随意一个未被配对的点u開始,从点u的边中随意选一条边(假设这条边是)開始配对。假设此时点v还没有被配对,则配对成功,此时便找到了一条增广路()。假设此时点v已经被配对了,那就要尝试进行”连锁反应”。
假设尝试成功了,则找到一条增广路,此时须要更新原来的配对关系。这里用一个数组match来记录配对关系,比方点v与点u配对了,就记作match[v]=u和match[u]=v。
配对成功后。将配对数+1。
配对的过程我们能够通过深度优先搜索来实现,当然广度优先搜索也能够。
(2)假设刚才所选的边配对失败,要从点u的边中再又一次选一条边,进行尝试。
直到点u配对成功,或者尝试过点u的全部点为止。
(3)接下来继续对剩下没有被配对的点一一进行配对,知道全部的点都尝试完成,找不到新的增广路为止。
(4)输出配对数
模板代码:
int book[Maxn],e[Maxn][Maxn],match[Maxn];int DFS(){ FOR(i,1,n)//n个点{if(!book[i]&& e[u][i]){book[i]=1;//标记点i已经訪问过if(!match[]||DFS(match[i])){Match[i]=u;return1;}}}return0;}intMaxMatch(){int res=0;mem(match);FOR(i,1,n){ mem(book);if(DFS(i))res++:}return res;}
概念:
点覆盖集即一个点集，使得全部边至少有一个端点在集合里。或者说是“点” 覆盖了全部“边”。
极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。
最小点覆盖(minimum vertex covering)：点最少的点覆盖。
点覆盖数(vertex covering number)：最小点覆盖的点数。
边覆盖集即一个边集。使得全部点都与集合里的边邻接。或者说是“边” 覆盖了全部“点”。
极小边覆盖(minimal edge covering)：本身是边覆盖。其真子集都不是。
最小边覆盖(minimum edge covering)：边最少的边覆盖。
边覆盖数(edge covering number)：最小边覆盖的边数。
独立集即一个点集。集合中任两个结点不相邻。则称V为独立集。
或者说是导出的子图是零图（没有边）的点集。
极大独立集(maximal independent set)：本身为独立集，再增加不论什么点都不是。
最大独立集(maximum independent set)：点最多的独立集。
独立数(independent number)：最大独立集的点。
团即一个点集。集合中任两个结点相邻。或者说是导出的子图是全然图的点集。
极大团(maximal clique)：本身为团，再增加不论什么点都不是。
最大团(maximum clique)：点最多的团。
团数(clique number)：最大团的点数。
边独立集即一个边集，满足边集中的任两边不邻接。
极大边独立集(maximal edge independent set)：本身为边独立集，再增加不论什么边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。
边独立数(edge independent number)：最大边独立集的边数。
边独立集又称匹配(matching)。对应的有极大匹配(maximal matching)，最大匹配(maximum matching)，匹配数(matching number)。
支配集即一个点集，使得全部其它点至少有一个相邻点在集合里。或者说是一部分的“点”支配了全部“点”。
极小支配集(minimal dominating set)：本身为支配集。其真子集都不是。
最小支配集(minimum dominating set)：点最少的支配集。
支配数(dominating number)：最小支配集的点数。
边支配集即一个边集。使得全部边至少有一条邻接边在集合里。
或者说是一部分的“边”支配了全部“边”。
极小边支配集(minimal edge dominating set)：本身是边支配集，其真子集都不是。
最小边支配集(minimum edge dominating set)：边最少的边支配集。
边支配数(edge dominating number)：最小边支配集的边数。
最小路径覆盖(path covering)：是“路径” 覆盖“点”。即用尽量少的不相交简单路径覆盖有向无环图G的全部顶点，即每一个顶点严格属于一条路径。路径的长度可能为0(单个点)。
最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，可是又不能让两条边在同一个顶点相交。
拆点：将每个顶点i拆成两个顶点Xi和Yi。
然后依据原图中边的信息。从X部往Y部引边。
全部边的方向都是由X部到Y部。因此。所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便能够得解。
匹配(matching)是一个边集。满足边集中的边两两不邻接。
匹配又称边独立集(edge independent set)。
在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。
交错轨(alternating path)是图的一条简单路径。满足随意相邻的两条边，一条在匹配内。一条不在匹配内。
增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。
最大匹配(maximum matching)是具有最多边的匹配。
匹配数(matching number)是最大匹配的大小。
完美匹配(perfect matching)是匹配了全部点的匹配。
完备匹配(complete matching)是匹配了二分图较小集合（二分图X。Y中小的那个）的全部点的匹配。
增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。
全部匹配算法都是基于增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。这个定理适用于随意图。
二分图的性质:
(1)二分图的最大匹配数等于最小覆盖数。即求最少的点使得每条边都至少和当中的一个点相关联，非常显然直接取最大匹配的一段节点就可以。
(2) 二分图的独立数等于顶点数减去最大匹配数，非常显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同一时候必定能够从每条匹配边的两端取一个点增加独立集而且保持其独立集性质。
(3) DAG的最小路径覆盖。将每一个点拆点后作最大匹配，结果为n-m，求详细路径的时候顺着匹配边走就能够，匹配边i→j',j→k',k→l'....构成一条有向路径。
(4)最大匹配数=左边匹配点+右边未匹配点。
由于在最大匹配集中的随意一条边。假设他的左边没标记，右边被标记了，那么我们就可找到一条新的增广路，所以每一条边都至少被一个点覆盖。
(5)最小边覆盖=-最大匹配数=最大独立集。
(6)最小覆盖数 = 最大匹配数
(7)最大独立集S 与 最小覆盖集T 互补
二分图的判定
二分图是这样一个图： 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每一个顶点集中没有边直接相连接！
无向图G为二分图的充分必要条件是，G至少有两个顶点,且其全部回路的长度均为偶数。
推断二分图的常见方法是染色法： 開始对随意一未染色的顶点染色，之后推断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色同样则说明不是二分图，若颜色不同则继续推断，bfs和dfs能够搞定。
易知：不论什么无回路的的图均是二分图。
二分图带权最优匹配
二分图带权最优匹配：对于二分图的每条边都有一个权（非负）。要求一种完备匹配方案。使得全部匹配边的权和最大，记做最优完备匹配。（特殊的。当全部边的权为1时，就是最大完备匹配问题）
二分最大匹配：使得匹配中的边数量不小于不论什么其它的匹配。
二分完备匹配：使得图G中全部点出如今该匹配中。
3.Kuhn-Munkers算法
斯坦纳树
最小生成树
1.Kruskal算法:按边权排序,每次从剩余的边中选择权值最小且边的两个顶点不在同一集合内(并查集)的边增加到生成树,直到增加了n-1条边
//Kruskal算法核心部分FOR(i,1,m){if(merge(e[i].u,e[i].v)){count++;sum+=e[i].w;}if(count==n-1)breal;}
(1)从随意一个顶点開始构造生成树,最好还是设从1号顶点開始,将顶点1增加生成树,用一个一维数组book来标记哪些顶点已经增加了生成树
(2)用数组dis记录生成树到各个顶点的距离。最初生成树中仅仅有1号顶点,有直连边时,数组dis中存储的就是1号顶点到该顶点的边的权值,没有直连边的时候就是无穷大,即初始化dis数组
(3)从数组dis中选出距离生成树近期的顶点(如果这个顶点为j)增加到生成树中(即在dis 数组中找最小值)。再以j为中间点,更新生成树到每个非树顶点的距离(松弛),即如果dis[k]>e[j][k]则更新dis[k]=e[j][k]。
(4)反复第(3)步,直到生成树中有n个顶点为止。
//Prim核心部分//将一号顶点增加生成树book[1]=1;//用book数组标记顶点i是否增加生成树count++;while(count<n){ min=inf;FOR(i,1,n){if(!book[i]&& dis[i]<min){min=dis[i];j=i;}book[j]=1;//扫描当前顶点j全部的边,再以j为中间点,更新生成树到每个非树顶点的距离FOR(k,1,n){if(!book[k])dis[k]=min(,dis[k]e[j][k]);}}}
Sollin（Boruvka)算法
网络流
最大流最小割定理
对于一个流网络G=(E,V)，一下三个命题两两等价
1）f是G的一个最大流
2）残余网络Gf不存在增广路径
3）对于G的某个割（S,T），f=c(S,T)且c(S,T)是G的某个最小割
Ford-Fulkerson方法（增大路径最大流方法）
(1)初始化网络中全部边的容量,继承该边的容量,初始化为0,当中边即为回退边。初始化最大流为0。
(2)在残留网络中找一条从源S到汇T的增广路p。如能找到,则转步骤(3),如不能,则转步骤(5)
(3)在增广路中找到所谓的”瓶颈”边,即路径中容量最小的边,记录下这个值X,而且累加到最大流中,转步骤(4)
(4)将增广路中全部减去X,全部加上X,构成新的残留网络。转步骤(2)
(5)得到最大流,退出
Edmonds-Karp（EK）算法
Dinic算法
SAP算法(最短路径增广算法)
Preflow push method(预流-推进最大流方法）
Relabel to front 算法（重标记与前移算法）
最高标号预流推进算法
最小费用最大流问题求解算法有
1、 连续最短路算法（Successive Shortest Path）；
2、 消圈算法（Cycle Canceling）；
3、 原始对偶算法（Primal Dual）；
4、 网络单纯形（Network Simplex）。
数据结构
1.线段树
//单点更新,区间查询#defineMaxn55555#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int sum[Maxn<<2];voidPushUP(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void build(int l,int r,int rt){if(l==r){scanf("%d",&sum[rt]);return;}int m=(l+r)>>1;build(lson);build(rson);PushUP(rt);}void update(int p,int add,int l,int r,int rt){if(l==r){sum[rt]+=add;return;}int m=(l+r)>>1;if(p<=m)update(p,add,lson);else update(p,add,rson);PushUP(rt);}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return sum[rt];int m=(l+r)>>1;int ret=0;if(L <=m ) ret+=query(L,R,lson);if(R>m) ret+=query(L,R,rson);return ret;}int main(){int n,T;scanf("%d",&T);FOR(m,1,T){ printf("Case %d:\n",m);scanf("%d",&n);build(1,n,1);char op[10];while(scanf("%s",op)){if(op[0]=='E')break;int a,b;scanf("%d%d",&a,&b);if(op[0]=='Q') printf("%d\n",query(a,b,1,n,1));elseif(op[0]=='S') update(a,-b,1,n,1);else update(a,b,1,n,1);}}return0;}
//单点更新,区间最值查询#defineMaxn222222#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int MAX[Maxn<<2];voidPushUP(int rt){ MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);}void build(int l,int r,int rt){if(l==r){scanf("%d",&MAX[rt]);return;}int m=(l+r)>>1;build(lson);build(rson);PushUP(rt);}void update(int p,int sc,int l,int r,int rt){if(l==r){MAX[rt]=sc;return;}int m=(l+r)>>1;if(p<=m) update(p,sc,lson);else update(p,sc,rson);PushUP(rt);}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return MAX[rt];int m=(l+r)>>1;int ret=0;if(L<=m) ret = max(ret,query(L,R,lson));if(R>m) ret = max(ret,query(L,R,rson));return ret;}int main(){int n,m;while(~scanf("%d%d",&n,&m)){ build(1,n,1);while(m--){char op[2];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0]=='Q') printf("%d\n",query(a,b,1,n,1));else update(a,b,1,n,1);}}return0;}
//成段更新,Lazy标记#defineMaxn111111#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int h,w,n;int col[Maxn<<2];int sum[Maxn<<2];voidPushUP(int rt){sum[rt]= sum[rt<<1]+ sum[rt<<1|1];}voidPushDown(int rt,int m){if(!col[rt]){col[rt<<1]= col [rt<<1|1]= col[rt];sum[rt<<1]=(m-(m>>1))*col[rt];sum[rt<<1|1]=(m>>1)*col[rt];col[rt]=0;}}void build(int l,int r,int rt){ col[rt]=0;sum[rt]=1;if(l==r)return;int m=(l+r)>>1;build(lson);build(rson);PushUP(rt);}void update(int L,int R,int c,int l,int r,int rt){if(L <= l && r<=R){col[rt]= c;sum[rt]= c*(r-l+1);return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)update(L,R,c,lson);if(R>m) update(L,R,c,rson);PushUP(rt);}int main(){int T,n,m;while(~scanf("%d",&T)){ memset(col,-1,sizeof col);memset(sum,0,sizeof sum);FOR(cas,1,T){ scanf("%d%d",&n,&m);build(1,n,1);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);update(a,b,c,1,n,1);}printf("Case %d:The total value of the hook is %d\n",cas,sum[1]);}}return0;}
void init()//初始化{ FOR(i,1,n) f[i]=i;}int getf(int v){if(f[v]==v)return v;else{ f[v]=getf(f[v]);return f[v];}}void merge(int v ,int u){int t1,t2;t1=getf(v);t2=getf(u);if(t1!=t2)f[t2]=t1;}
3.二叉堆
最小堆:父结点都比子结点小
最大堆:父结点都比子结点大
4.树状数组
intLowbit(){return i&(-i);}//2^k,k为i在二进制下末尾0的个数intUpdate(int i,int x){while(i<=n){c[i]+=x;i+=Lowbit(i);}}int sum(int n)//前n项和{int sum=0;While(n){sum+=c[n];n-=Lowbit(n);}return sum;}
多维树状数组:
5.Treap(树堆)
Treap=Tree(BST)+Heap(最小堆)。
Treap须要维护两个值,一个是二叉搜索树中的key,一个是最小堆中的优先值(aux)。
Treap是一棵aux值满足最小堆性质的BST。
Treap的旋转操作不会影响它的BST性质,当不满足堆性质时,能够通过旋转操作使它满足堆性质。
6.Splay(伸展树)
7.树链剖分
8.主席树
9.BST
性质:若它的左子树不空，则左子树上全部结点的值均小于它的根结点的值。 若它的右子树不空，则右子树上全部结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
//推断两序列是否为同一二叉搜索树#include<iostream>#include<cstdio>#include<cstring>usingnamespace std;int num1[N],num2[N];voidInsert(int num[N],int index,int x){if(num[index]==-1){num[index]=x;return;}if(num[index]<x)Insert(num,index<<1,x);elseInsert(num,index<<1|1,x);}int main(){ //freopen("input.txt","r",stdin);int n;memset(num1,-1,sizeof(num1));scanf("%s",str);for(int i=0;str[i]!='\0';i++){int x=str[i]-'0';Insert(num1,1,x);}int flag;while(n--){scanf("%s",str);flag=1;memset(num2,-1,sizeof(num2));for(int j=0;str[j]!='\0';j++){int x=str[j]-'0';Insert(num2,1,x);}for(int j=0;j<N;j++)if(num1[j]!=num2[j]){flag=0;break;}if(flag)puts("YES");elseputs("NO");}}return0;}
字符串
KMP算法
Next数组事实上就是查找每一位的子串的前后缀有多少位匹配,从而决定匹配失败时退回到哪个位置
Trie树
利用字符串的公共前缀来减少查询时间的开销,以空间换时间
(1)根节点不包括字符,除根节点以外,每一个节点都仅仅包括一个字符
(2)从根节点到某一节点,路径上的字符连接起来为该节点相应的字符串
(3)每一个节点的全部子节点包括的字符都不同样
时间复杂度O(n)空间复杂度O(26^n)
构建trie树
struct node{struct node *next[26];bool value;node(){FOR(i,0,25)next[i]=NULL;value=false;}}*root;voidInsert(char s[]){int k =0;node *p =root;while(s[k]!='\0'){if(!p->next[s[k]-'a'])p->next[s[k]-'a']=new node();p=p->next[s[k]-'a'];k++;}p->value=true;}boolFind(char s[]){int k=0;node *p=root;while(s[k]!='\0'&& p->next[s[k]-'a']){ p=p->next[s[k]-'a'];k++;}if(s[k]=='\0'&&p->value)return p->value;returnfalse;}
AC自己主动机
后缀树
后缀数组
后缀自己主动机
參考文献与资料
[1]《啊哈!算法》
[2]《ACM-ICPC程序设计系列 算法设计与实现》
[3]《背包九讲》
[4]《ACM国际大学生程序设计竞赛 知识与入门》
[5]《ACM国际大学生程序设计竞赛 算法与实现》
[6]《算法导论》