Gusfield算法学习-6ren

Gusfield算法学习

转载作者：我是一只小鸟更新时间：2023-04-29 22:31:34

算法详解

等价流树正如其名，树上两点间的路径上的边权最小值为图上两点间的最小割.

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年王文涛国集论文。

例题

1. 【模板】最小割树（Gomory-Hu Tree）。

其实我并不觉得这是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]最小割。

也是个板题，建出等价流树，如果不连通，就每个连通块之间建一条长度为 \(0\) 的边，最后询问时在树上以每个点为起点扫一遍即可.

点击查看代码

                          
                            #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算法学习的文章就讲到这里了,如果你想了解更多关于Gusfield算法学习的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： Django笔记三十四之分页操作

文章推荐： GPT护理机器人-让护士的工作变简单

文章推荐：驱动开发：通过MDL映射实现多次通信

算法~利用zset实现滑动窗口限流
滑动窗口限流滑动窗口限流是一种常用的限流算法，通过维护一个固定大小的窗口，在单位时间内允许通过的请求次数不超过设定的阈值。具体来说，滑动窗口限流算法通常包括以下几个步骤：初始化：设置窗口
【算法】表达式求值
表达式求值：一个只有+,-,*,/的表达式，没有括号一种神奇的做法：使用数组存储数字和运算符，先把优先级别高的乘法和除法计算出来，再计算加法和减法 int GetVal(string s){
【算法】前缀和
【算法】前缀和题目先来看一道题目：（前缀和模板题）已知一个数组A[]，现在想要求出其中一些数字的和。输入格式：先是整数N,M，表示一共有N个数字，有M组询问接下来有N个数，表示A[1]..
【算法】二叉树的各种遍历方式
1.前序遍历根-左-右的顺序遍历，可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
【算法】01背包
先看题目物品不能分隔，必须全部取走或者留下，因此称为01背包（只有不取和取两种状态）看第一个样例我们需要把4个物品装入一个容量为10的背包我们可以简化问题，从小到大入手分析 weightva
算法 - 矩阵中被另一种颜色包围的颜色
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
使用Outlook发送电子邮件的C++算法
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件，该帐户已经打开并记录，但真的不知道从哪里开始(对于 outlook-c++ 集成)，谷歌也没有帮我这么多。任何提示将不胜感激。
容器上滑动窗口的C++算法
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
检测正方形后运行命令的c++算法
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后，代码运行另一个命令。代码如下: #include "cv.h" #include "cxcore.h" #include "high
二值图像的泛洪填充C++算法
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。我想在矩阵中指定一个起点，并像 imfill 的 4 连接版本那样进行洪水填充。这是否已经存在于
算法递归公式
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
算法 - 如何生成日期结构？
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录，如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
算法:查找恰好出现两次的元素
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
算法——基于寻找最大匹配数
我遇到了一个问题，但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点，但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
算法 - 用于计算成对相互出现的次数
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值，那么我会得到一个列表 L2。我有另一个列表 L3，它是 L2 的某个
算法 - 在矩阵中求和
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2，因为4+4=8 >= 7，
算法:根据周数获取下一年日期工作类次类型
我实行 3 类倒制，每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单，即它永远不会改变，即使那个星期不工作也是如此。我创建了一个函数来获取 ISO 周数。当我给它一个日期时
算法 - 找到满足输入元素任意组合的所有集合
假设我们有一个输入，它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合，可能包含这些元素的任意组合，也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
算法:添加新元素时如何找到集合的子集？
我有一个子集算法，可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合，如果向其中添加元素，我需要再次重新计算它的子集。有没有一种方法可以优化子集算法，该算法可以从最后一个计算点重新
算法:按预期频率将符号压缩成位串？
我有一个包含 100 万个符号及其预期频率的表格。我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列，然后将它们连接在一起以表示序列。我想分配这些位串，以使编码序列的预

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

Gusfield算法学习

算法详解

例题