LoLiK

歸納（二）：倍增

關于倍增的學習

何為倍增

把一步一步往上爬變成一次一次向前跳，從\(O(n)->O(log_{n})\)的蛻變，可以解決很多問題。

倍增的精髓

\[anc[i][k]=anc[anc[i][k-1]][k-1] \]

就這么一行。
我的\(2^{k}\)級祖先就是我\(2^{k-1}\)級祖先的\(2^{k-1}\)級祖先。

就憑這句話，就可以解決很多問題了。

例題（一）：裸題就是神題

洛谷P1613跑路

小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\n",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\n",lca(a,b));
    }
    return 0;
}

例題（三）：稍顯正經

洛谷P1967 貨車運輸

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\n",lca(read(),read()));
    return 0;
}

一些問題：

看不出來怎么辦？

如果不是看算法標簽，或許我完全想不到倍增這種做法，但不管怎樣，還是總結一下。
常見題型：

LCA
帶\(2^{k}\)的計算
......

其實最重要的是多做題是吧。

做不出來怎么辦？

對著那個式子一直想一直想。

或許吧。。。

posted @ 2018-10-09 10:19 LoLiK 閱讀(314) 評論(0) 收藏舉報

刷新頁面返回頂部