> 科技资讯 > Gusfield算法学习

Gusfield算法学习

科技资讯 投稿 5000℃ 0 评论

Gusfield算法学习

算法详解

Gusfield算法就是建等价流树的一种算法。设当前正在处理的集合为 \(S(|S|\ge 2\，从 \(S\ 中任选两个点 \(x,y\，求出 \(x,y\ 间的最小割也就是最大流 \(flow\，此时在最小割树中加入一条从 \(x\ 到 \(y\，边权为 \(flow\。在原图中去掉所有的满流边后，\(S\ 会变成两部分，一部分是在残量网络上从起点能遍历到的点，另一部分是遍历不到的点，分治下去求解即可，很容易可以发现，最多求解 \(n-1\ 次，所以得到的必然是棵树。

有一种不严谨的证明，因为递归出来的两边都是合法的等价流树，假设这两棵等价流树中的边权全部大于 \((s,t\ 这条边，那么显然割掉 \((s,t\ 代表的原图中的边集会优于割掉其它边代表的原图中的边集。即若存在 \(u,v\ 分别再 \(s,t\ 侧，\((s,t\ 这条边的边权必然为 \(u,v\ 的最小割。至于更详细的证明可以研读2016年王文涛国集论文

例题

其实我并不觉得这是GHT的模板，它只用到了大小，并没有用到方案等其它信息。直接建出等价流树，每次询问在等价流树上找路径边权最小值即可，倍增预处理皆可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x{
        x=0;
        int f=1;
        char ch=getchar(;
        while(ch>'9'||ch<'0'{
            if(ch=='-'{
                f=-1;
            }
            ch=getchar(;
        }
        while(ch>='0'&&ch<='9'{
            x=x*10+(ch-'0';
            ch=getchar(;
        }
        x=(f==1?x:-x;
    }
    template<typename T>
    inline void write(T x{
        if(x<0{
            putchar('-';
            x=-x;
        }
        if(x>=10{
            write(x/10;
        }
        putchar(x%10+'0';
    }
    template<typename T>
    inline void write_endl(T x{
        write(x;
        putchar('\n';
    }
    template<typename T>
    inline void write_space(T x{
        write(x;
        putchar(' ';
    }
}
using namespace IO;
const int N=510,M=6010,Lg=11,inf=1e9;
int n,m,head[N],hd[N],tot1=0,tot=1,id[N];
struct edge{
    int v,w,nxt;
}e[M],G[M];
void add(int u,int v,int w{
    e[++tot].v=v;
    e[tot].nxt=head[u];
    e[tot].w=w;
    head[u]=tot;
}
void add1(int u,int v,int w{
    G[++tot1].v=v;
    G[tot1].w=w;
    G[tot1].nxt=hd[u];
    hd[u]=tot1;
}
namespace GHT{
    int dep[N],cur[N],tmp1[N],tmp2[N];
    bool bfs(int S,int T{
        for(int i=1;i<=n;i++{
            dep[i]=0;
        }
        queue<int>q;
        q.push(S;
        dep[S]=1;
        while(!q.empty({
            int u=q.front(;
            q.pop(;
            for(int i=head[u];i;i=e[i].nxt{
                int v=e[i].v,w=e[i].w;
                if(w&&!dep[v]{
                    dep[v]=dep[u]+1;
                    q.push(v;
                    if(v==T{
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int dfs(int u,int flow,int T{
        if(u==T{
            return flow;
        }
        int s=0;
        for(int i=cur[u];i;i=e[i].nxt{
            cur[u]=i;
            int v=e[i].v,w=e[i].w;
            if(w&&dep[v]==dep[u]+1{
                int res=dfs(v,min(flow,w,T;
                e[i].w-=res;
                e[i^1].w+=res;
                flow-=res;
                s+=res;
            }
            if(!flow{
                break;
            }
        }
        if(!s{
            dep[u]=0;
        }
        return s;
    }
    void init({
        for(int i=0;i<=tot;i+=2{
            e[i].w+=e[i^1].w;
            e[i^1].w=0;
        }
    }
    int dinic(int S,int T{
        init(;
        int ans=0;
        while(bfs(S,T{
            memcpy(cur,head,sizeof(head;
            ans+=dfs(S,inf,T;
        }
        return ans;
    }
    void build(int l,int r{
        if(l>=r{
            return;
        }
        int x=id[l],y=id[l+1];
        int flow=dinic(x,y;
        add1(x,y,flow;
        add1(y,x,flow;
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++{
            if(dep[id[i]]{
                tmp1[++cnt1]=id[i];
            }
            else{
                tmp2[++cnt2]=id[i];
            }
        }
        for(int i=1;i<=cnt1;i++{
            id[l+i-1]=tmp1[i];
        }
        for(int i=1;i<=cnt2;i++{
            id[cnt1+i+l-1]=tmp2[i];
        }
        build(l,l+cnt1-1;
        build(l+cnt1,r;
    }
}
int f[N][Lg+5],mn[N][Lg+5],dep[N];
void make_tree(int u,int father{
    f[u][0]=father;
    dep[u]=dep[father]+1;
    for(int i=1;i<=Lg;i++{
        f[u][i]=f[f[u][i-1]][i-1];
        mn[u][i]=min(mn[u][i-1],mn[f[u][i-1]][i-1];
    }
    for(int i=hd[u];i;i=G[i].nxt{
        int v=G[i].v,w=G[i].w;
        if(v==father{
            continue;
        }
        mn[v][0]=w;
        make_tree(v,u;
    }
}
int lca(int u,int v{
    if(dep[u]<dep[v]{
        swap(u,v;
    }
    int mini=inf;
    for(int i=Lg;i>=0;i--{
        if(dep[f[u][i]]>=dep[v]{
            mini=min(mini,mn[u][i];
            u=f[u][i];
        }
    }
    if(u==v{
        return mini;
    }
    for(int i=Lg;i>=0;i--{
        if(f[u][i]!=f[v][i]{
            mini=min(mini,min(mn[u][i],mn[v][i];
            u=f[u][i],v=f[v][i];
        }
    }
    return min(mini,min(mn[u][0],mn[v][0];
}
signed main({
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin;
        freopen("1.out","w",stdout;
    #endif
    memset(mn,0x3f,sizeof(mn;
    read(n,read(m;
    for(int i=1,u,v,w;i<=m;i++{
        read(u,read(v,read(w;
        add(u,v,w;
        add(v,u,0;
        add(v,u,w;
        add(u,v,0;
    }
    for(int i=1;i<=n;i++{
        id[i]=i;
    }
    GHT::build(1,n;
    make_tree(1,0;
    int q;
    read(q;
    while(q--{
        int u,v;
        read(u,read(v;
        write_endl(lca(u,v;
    }
    return 0;
}

2.[ZJOI2011]最小割

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x{
        x=0;
        int f=1;
        char ch=getchar(;
        while(ch>'9'||ch<'0'{
            if(ch=='-'{
                f=-1;
            }
            ch=getchar(;
        }
        while(ch>='0'&&ch<='9'{
            x=x*10+(ch-'0';
            ch=getchar(;
        }
        x=(f==1?x:-x;
    }
    template<typename T>
    inline void write(T x{
        if(x<0{
            putchar('-';
            x=-x;
        }
        if(x>=10{
            write(x/10;
        }
        putchar(x%10+'0';
    }
    template<typename T>
    inline void write_endl(T x{
        write(x;
        putchar('\n';
    }
    template<typename T>
    inline void write_space(T x{
        write(x;
        putchar(' ';
    }
}
using namespace IO;
const int N=510,M=60010,inf=1e12;
int n,m,head[N],hd[N],tot1=0,tot=1,id[N],fa[N];
struct edge{
    int v,w,nxt;
}e[M],G[M];
int getfa(int x{
    if(fa[x]!=x{
        fa[x]=getfa(fa[x];
    }
    return fa[x];
}
void merge(int u,int v{
    u=getfa(u,v=getfa(v;
    if(u!=v{
        fa[v]=u;
    }
}
void add(int u,int v,int w{
    e[++tot].v=v;
    e[tot].nxt=head[u];
    e[tot].w=w;
    head[u]=tot;
}
void add1(int u,int v,int w{
    G[++tot1].v=v;
    G[tot1].w=w;
    G[tot1].nxt=hd[u];
    hd[u]=tot1;
    merge(u,v;
}
namespace GHT{
    int dep[N],cur[N],tmp1[N],tmp2[N];
    bool bfs(int S,int T{
        for(int i=1;i<=n;i++{
            dep[i]=0;
        }
        queue<int>q;
        q.push(S;
        dep[S]=1;
        while(!q.empty({
            int u=q.front(;
            q.pop(;
            for(int i=head[u];i;i=e[i].nxt{
                int v=e[i].v,w=e[i].w;
                if(w&&!dep[v]{
                    dep[v]=dep[u]+1;
                    q.push(v;
                    if(v==T{
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int dfs(int u,int flow,int T{
        if(u==T{
            return flow;
        }
        int s=0;
        for(int i=cur[u];i;i=e[i].nxt{
            cur[u]=i;
            int v=e[i].v,w=e[i].w;
            if(w&&dep[v]==dep[u]+1{
                int res=dfs(v,min(flow,w,T;
                e[i].w-=res;
                e[i^1].w+=res;
                flow-=res;
                s+=res;
            }
            if(!flow{
                break;
            }
        }
        if(!s{
            dep[u]=0;
        }
        return s;
    }
    void init({
        for(int i=0;i<=tot;i+=2{
            e[i].w+=e[i^1].w;
            e[i^1].w=0;
        }
    }
    int dinic(int S,int T{
        init(;
        int ans=0;
        while(bfs(S,T{
            memcpy(cur,head,sizeof(head;
            ans+=dfs(S,inf,T;
        }
        return ans;
    }
    void build(int l,int r{
        if(l>=r{
            return;
        }
        int x=id[l],y=id[l+1];
        int flow=dinic(x,y;
        add1(x,y,flow;
        add1(y,x,flow;
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++{
            if(dep[id[i]]{
                tmp1[++cnt1]=id[i];
            }
            else{
                tmp2[++cnt2]=id[i];
            }
        }
        for(int i=1;i<=cnt1;i++{
            id[l+i-1]=tmp1[i];
        }
        for(int i=1;i<=cnt2;i++{
            id[cnt1+i+l-1]=tmp2[i];
        }
        build(l,l+cnt1-1;
        build(l+cnt1,r;
    }
}
void clear({
    for(int i=1;i<=n;i++{
        head[i]=hd[i]=0;
        id[i]=i;
        fa[i]=i;
    }
    tot=tot1=1;
}
int ans,x;
void dfs(int u,int father,int mn{
    if(mn<=x{
        ans++;
    }
    for(int i=hd[u];i;i=G[i].nxt{
        int v=G[i].v,w=G[i].w;
        if(v==father{
            continue;
        }
        dfs(v,u,min(mn,w;
    }
}
void solve({
    read(n,read(m;
    clear(;
    for(int i=1,u,v,w;i<=m;i++{
        read(u,read(v,read(w;
        add(u,v,w;
        add(v,u,0;
        add(v,u,w;
        add(u,v,0;
    }
    GHT::build(1,n;
    for(int i=2;i<=n;i++{
        if(getfa(i!=getfa(1{
            add1(i,1,0;
            merge(1,i;
        }
    }
    int q;
    read(q;
    while(q--{
        read(x;
        ans=0;
        for(int i=1;i<=n;i++{
            dfs(i,0,inf;
        }
        write_endl(ans/2;
    }

}
signed main({
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin;
        freopen("1.out","w",stdout;
    #endif
    int t;
    read(t;
    while(t--{
        solve(;
        puts("";
    }
    return 0;
}

3.[CQOI2016]不同的最小割

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x{
        x=0;
        int f=1;
        char ch=getchar(;
        while(ch>'9'||ch<'0'{
            if(ch=='-'{
                f=-1;
            }
            ch=getchar(;
        }
        while(ch>='0'&&ch<='9'{
            x=x*10+(ch-'0';
            ch=getchar(;
        }
        x=(f==1?x:-x;
    }
    template<typename T>
    inline void write(T x{
        if(x<0{
            putchar('-';
            x=-x;
        }
        if(x>=10{
            write(x/10;
        }
        putchar(x%10+'0';
    }
    template<typename T>
    inline void write_endl(T x{
        write(x;
        putchar('\n';
    }
    template<typename T>
    inline void write_space(T x{
        write(x;
        putchar(' ';
    }
}
using namespace IO;
const int N=1010,M=600010,Lg=11,inf=1e9;
int n,m,head[N],hd[N],tot1=0,tot=1,id[N];
struct edge{
    int v,w,nxt;
}e[M];
void add(int u,int v,int w{
    e[++tot].v=v;
    e[tot].nxt=head[u];
    e[tot].w=w;
    head[u]=tot;
}
set<int>s;
namespace GHT{
    int dep[N],cur[N],tmp1[N],tmp2[N];
    bool bfs(int S,int T{
        for(int i=1;i<=n;i++{
            dep[i]=0;
        }
        queue<int>q;
        q.push(S;
        dep[S]=1;
        while(!q.empty({
            int u=q.front(;
            q.pop(;
            for(int i=head[u];i;i=e[i].nxt{
                int v=e[i].v,w=e[i].w;
                if(w&&!dep[v]{
                    dep[v]=dep[u]+1;
                    q.push(v;
                    if(v==T{
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int dfs(int u,int flow,int T{
        if(u==T{
            return flow;
        }
        int s=0;
        for(int i=cur[u];i;i=e[i].nxt{
            cur[u]=i;
            int v=e[i].v,w=e[i].w;
            if(w&&dep[v]==dep[u]+1{
                int res=dfs(v,min(flow,w,T;
                e[i].w-=res;
                e[i^1].w+=res;
                flow-=res;
                s+=res;
            }
            if(!flow{
                break;
            }
        }
        if(!s{
            dep[u]=0;
        }
        return s;
    }
    void init({
        for(int i=0;i<=tot;i+=2{
            e[i].w+=e[i^1].w;
            e[i^1].w=0;
        }
    }
    int dinic(int S,int T{
        init(;
        int ans=0;
        while(bfs(S,T{
            memcpy(cur,head,sizeof(head;
            ans+=dfs(S,inf,T;
        }
        return ans;
    }
    void build(int l,int r{
        if(l>=r{
            return;
        }
        int x=id[l],y=id[l+1];
        int flow=dinic(x,y;
        s.insert(flow;
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++{
            if(dep[id[i]]{
                tmp1[++cnt1]=id[i];
            }
            else{
                tmp2[++cnt2]=id[i];
            }
        }
        for(int i=1;i<=cnt1;i++{
            id[l+i-1]=tmp1[i];
        }
        for(int i=1;i<=cnt2;i++{
            id[cnt1+i+l-1]=tmp2[i];
        }
        build(l,l+cnt1-1;
        build(l+cnt1,r;
    }
}
signed main({
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin;
        freopen("1.out","w",stdout;
    #endif
    read(n,read(m;
    for(int i=1,u,v,w;i<=m;i++{
        read(u,read(v,read(w;
        add(u,v,w;
        add(v,u,0;
        add(v,u,w;
        add(u,v,0;
    }
    for(int i=1;i<=n;i++{
        id[i]=i;
    }
    GHT::build(1,n;
    write_endl(s.size(;
    return 0;
}

4.cf343e

    洛谷题面
  • CF题面

此时我们再看一下一个排列表示什么，表示的是给每个点标一个dfs序，然后按照dfs序在最小割树上搜一遍，因为等价流树的性质，所以最小割的和等于dfs序相邻的两点的路径上边权最小值的和。所以问题就转化为了求一个dfs序，使得最小割树上边权小的边尽量少走。

那么有可能造成更多的贡献吗？这是不可能的。
令最小边的两端点为 \(u,v\，若断掉最小边，则一棵树会变成两颗树，分别令 \(u,v\ 为根，那么这两棵树分别为树 \(u\ 和树 \(v\。一个非常显然的事是，我们可以先遍历完树 \(u\，再遍历树 \(v\，这样最小边就只会造成 \(1\ 次贡献，同理每条边都会造成 \(1\ 次贡献，答案的最大值就为等价流树上边权之和，方案可以 \(n^2\ 扫一遍。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x{
        x=0;
        int f=1;
        char ch=getchar(;
        while(ch>'9'||ch<'0'{
            if(ch=='-'{
                f=-1;
    }
            ch=getchar(;
        }
        while(ch>='0'&&ch<='9'{
            x=x*10+(ch-'0';
            ch=getchar(;
        }
        x=(f==1?x:-x;
    }
    template<typename T>
    inline void write(T x{
        if(x<0{
            putchar('-';
            x=-x;
        }
        if(x>=10{
            write(x/10;
        }
        putchar(x%10+'0';
    }
    template<typename T>
    inline void write_endl(T x{
        write(x;
        putchar('\n';
    }
    template<typename T>
    inline void write_space(T x{
        write(x;
        putchar(' ';
    }
}
using namespace IO;
const int N=300,M=1e4,inf=1e9;
int n,m,tot=1,tot1=1,head[N],hd[N],id[N],ans;
struct edge{
    int u,v,w,nxt;
}e[M],G[M];
void add(int u,int v,int w{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void add1(int u,int v,int w{
    G[++tot1].v=v;
    G[tot1].u=u;
    G[tot1].w=w;
    G[tot1].nxt=hd[u];
    ans+=w;
    hd[u]=tot1;
}
namespace Gusfield{
    int dep[N],cur[N],tmp1[N],tmp2[N];
    bool bfs(int S,int T{
        for(int i=1;i<=n;i++{
            dep[i]=0;
        }
        queue<int>q;
        q.push(S;
        dep[S]=1;
        while(!q.empty({
            int u=q.front(;
            q.pop(;
            for(int i=head[u];i;i=e[i].nxt{
                int v=e[i].v,w=e[i].w;
                if(w&&!dep[v]{
                    dep[v]=dep[u]+1;
                    q.push(v;
                    if(v==T{
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int dfs(int u,int flow,int T{
        if(u==T{
            return flow;
        }
        int s=0;
        for(int i=cur[u];i;i=e[i].nxt{
            cur[u]=i;
            int v=e[i].v,w=e[i].w;
            if(w&&dep[v]==dep[u]+1{
                int res=dfs(v,min(flow,w,T;
                e[i].w-=res;
                e[i^1].w+=res;
                flow-=res;
                s+=res;
            }
            if(!flow{
                break;
            }
        }
        if(!s{
            dep[u]=0;
        }
        return s;
    }
    void init({
        for(int i=0;i<=tot;i+=2{
            e[i].w+=e[i^1].w;
            e[i^1].w=0;
        }
    }
    int dinic(int S,int T{
        init(;
        int ans=0;
        while(bfs(S,T{
            memcpy(cur,head,sizeof(head;
            ans+=dfs(S,inf,T;
        }
        return ans;
    }
    void build(int l,int r{
        if(l>=r{
            return;
        }
        int x=id[l],y=id[l+1];
        int flow=dinic(x,y;
        add1(x,y,flow;
        add1(y,x,flow;
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++{
            if(dep[id[i]]{
                tmp1[++cnt1]=id[i];
            }
            else{
                tmp2[++cnt2]=id[i];
            }
        }
        for(int i=1;i<=cnt1;i++{
            id[l+i-1]=tmp1[i];
        }
        for(int i=1;i<=cnt2;i++{
            id[cnt1+i+l-1]=tmp2[i];
        }
        build(l,l+cnt1-1;
        build(l+cnt1,r;
    }
}
bool vis[M];
vector<int>s;
void get(int u,int fa{
    s.pb(u;
    for(int i=hd[u];i;i=G[i].nxt{
        int v=G[i].v;
        if(vis[i]||v==fa{
            continue;
        }
        get(v,u;
    }
}
void dfs(int u{
    if(s.size(==1{
        write_space(s[0];
        return;
    }
    int id=0,mn=inf;
    for(auto x:s{
        for(int i=hd[x];i;i=G[i].nxt{
            if(vis[i]{
                continue;
            }
            int w=G[i].w;
            if(w<mn{
                mn=w;
                id=i;
            }
        }
    }
    cerr<<id/2<<endl;
    vis[id]=vis[id^1]=1;
    vector<int>(.swap(s;
    get(G[id].u,0;
    dfs(G[id].u;
    vector<int>(.swap(s;
    get(G[id].v,0;
    dfs(G[id].v;
}
void solve({
    read(n,read(m;
    for(int i=1,u,v,w;i<=m;i++{
        read(u,read(v,read(w;
        add(u,v,w;
        add(v,u,0;
        add(v,u,w;
        add(u,v,0;
    }
    for(int i=1;i<=n;i++{
        id[i]=i;
    }
    Gusfield::build(1,n;
    write_endl(ans>>1;
    for(int i=1;i<=n;i++{
        s.pb(i;
    }
    dfs(1;
}
signed main({
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin;
        freopen("1.out","w",stdout;
    #endif
    int t=1;
    while(t--{
        solve(;
    }
    return 0;
}

编程笔记 » Gusfield算法学习

赞同 (26) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽