何为倍增
把一步一步往上爬变成一次一次向前跳，从(O(n)->O(log_{n}))的蜕变，可以解决很多问题。
倍增的精髓
[anc[i][k]=anc[anc[i][k-1]][k-1]
]
就这么一行。
我的(2^{k})级祖先就是我(2^{k-1})级祖先的(2^{k-1})级祖先。
就凭这句话，就可以解决很多问题了。
例题（一）：裸题就是神题
小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。
maxlongint是(2147483647)。
由于(n)只有50，于是就愉悦地用矩阵。
(t[i][j][k]) 表示(i,j)之间有没有长度为(2^{k})的边。
(dis[i][j]) 表示(i,j)之间的距离。
先处理可以用加速器的情况，在跑Floyd。
#include<bits/stdc++.h>
const int maxn=50+3;
bool t[maxn][maxn][35];
int dis[maxn][maxn];
int main() {
memset(dis,0x3f,sizeof(dis));
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int u,v;scanf("%d%d",&u,&v);
dis[u][v]=1;
t[u][v][0]=true;
}
for(int k=1;k<=31;k++)
for(int g=1;g<=n;g++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(t[i][g][k-1] && t[g][j][k-1]) {
t[i][j][k]=true;
dis[i][j]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
printf("%d
",dis[1][n]);
}
直接明示。
例题（二）：也许算是倍增的应用？
洛谷P3379【模板】最近公共祖先（LCA）
倍增求LCA算是最简单的应用了吧。
原理就是那一行代码。
向上跳的方法有多种，可以二进制拆位，也可以算(log_{2})
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=5e5+5;
struct Edge {
int v,nxt;
}e[maxn<<1];
int h[maxn],tot;
void add_edge(int u,int v) {
e[++tot].v=v;
e[tot].nxt=h[u];
h[u]=tot;
}
// 2^19 > MAXN
int n,m,root;
int anc[maxn][20],lg[maxn],dep[maxn];
void dfs(int nd,int p) {
dep[nd]=dep[p]+1;
anc[nd][0]=p;
for(int i=1;(1<<i)<=dep[p];i++)
anc[nd][i]=anc[anc[nd][i-1]][i-1];
for(int i=h[nd];~i;i=e[i].nxt)
if(e[i].v!=p) dfs(e[i].v,nd);
}
int lca(int x,int y) {
if(dep[x]<dep[y]) std::swap(x,y);
while(dep[x]>dep[y]) x=anc[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(int i=lg[dep[x]];i>=0;i--)
if(anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
int main() {
memset(h,-1,sizeof(h));
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(root,0);
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(int i=1;i<=m;i++) {
int a,b;scanf("%d%d",&a,&b);
printf("%d
",lca(a,b));
}
return 0;
}
例题（三）：稍显正经
Noip的题，相信都做过。
先搞一个最大生成树。
最小的那一条路怎么来的，路径上的所有边中的最小值。
于是求出每个点到LCA路径中的最小值再取min即可。
转移还是倍增，只需要再开一个数组(val[i][k]) 表示从(i)到它的第(2^{k})级祖先间的路径最小限重是多少。
于是就解决了。
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=1e4+5;
const int maxm=5e4+5;
const int oo=0x3f3f3f3f;
int read() {
int x;char ch;while(!isdigit(ch=getchar()));
for(x=ch-'0';isdigit(ch=getchar());x=(x<<3)+(x<<1)+ch-'0');
return x;
}
//graph
struct Edge {int nxt,v,f;}e[maxn<<1];
int h[maxn],tot,whi[maxn];
void add_edge(int u,int v,int f) {
e[++tot].v=v;e[tot].f=f;
e[tot].nxt=h[u];h[u]=tot;
}
//build MaX tree
struct Edg {int u,v,f;}E[maxm];
int fa[maxn];
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
bool cmp(const Edg &a,const Edg &b) {return a.f>b.f;}
//LCA
int anc[maxn][23],dep[maxn];
int val[maxn][23];
bool vis[maxn];
void dfs(int nd) {
vis[nd]=true;
for(int i=h[nd];~i;i=e[i].nxt)
if(!vis[e[i].v]) {
dep[e[i].v]=dep[nd]+1;
anc[e[i].v][0]=nd;
val[e[i].v][0]=e[i].f;
dfs(e[i].v);
}
return ;
}
int n,m;
int lg[maxn];
int lca(int x,int y) {
if(find(x)!=find(y)) return -1;
int ans=oo;
if(dep[x]<dep[y]) std::swap(x,y);
while(dep[x]>dep[y]) {
int delta=lg[dep[x]-dep[y]]-1;
ans=std::min(ans,val[x][delta]);
x=anc[x][delta];
}
if(x==y) return ans;
for(int k=lg[dep[x]];~k;k--) if(anc[x][k]!=anc[y][k]) {
ans=std::min(ans,std::min(val[x][k],val[y][k]));
x=anc[x][k],y=anc[y][k];
}
return std::min(ans,std::min(val[x][0],val[y][0]));
}
int main() {
memset(val,0x3f,sizeof(val));
memset(h,-1,sizeof(h));
n=read(),m=read();
for(int i=1;i<=m;i++)
E[i].u=read(),E[i].v=read(),E[i].f=read();
std::sort(E+1,E+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) {
if(find(E[i].u)==find(E[i].v)) continue;
int x=find(E[i].u),y=find(E[i].v);
fa[x]=y;
add_edge(E[i].u,E[i].v,E[i].f);
add_edge(E[i].v,E[i].u,E[i].f);
}
for(int i=1;i<=n;i++)
if(!vis[i]) {
dep[i]=1;
dfs(i);
anc[i][0]=i;
val[i][0]=oo;
}
for(int k=1;k<=20;k++)
for(int i=1;i<=n;i++) {
anc[i][k]=anc[anc[i][k-1]][k-1];
val[i][k]=std::min(val[i][k-1],val[anc[i][k-1]][k-1]);
}
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
int q=read();
while(q--) printf("%d
",lca(read(),read()));
return 0;
}
一些问题：
看不出来怎么办？
如果不是看算法标签，或许我完全想不到倍增这种做法，但不管怎样，还是总结一下。
常见题型：
LCA
带(2^{k})的计算
......
其实最重要的是多做题是吧。
做不出来怎么办？
对着那个式子一直想一直想。
或许吧。。。