POJ - 1459 Power Network（最大流）（模板）

1、看了好久，囧。

n个节点，np个源点，nc个汇点，m条边（对应代码中即节点u 到节点v 的最大流量为z）

求所有汇点的最大流。

2、多个源点，多个汇点的最大流。

建立一个超级源点、一个超级汇点，然后求超级源点到超级汇点的最大流即可。

3、

1、SAP邻接矩阵形式：

/*

SAP算法（矩阵形式）

结点编号从0开始

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;

int maze[MAXN][MAXN];

int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];

int sap(int start,int end,int nodenum){

    memset(cur,,sizeof(cur));

    memset(dis,,sizeof(dis));

    memset(gap,,sizeof(gap));

    int u=pre[start]=start,maxflow=,aug=-;

    gap[]=nodenum;

    while(dis[start]<nodenum){

        loop:

            for(int v=cur[u];v<nodenum;v++)

                if(maze[u][v]&&dis[u]==dis[v]+){

                    if(aug==-||aug>maze[u][v])aug=maze[u][v];

                    pre[v]=u;

                    u=cur[u]=v;

                    if(v==end){

                        maxflow+=aug;

                        for(u=pre[u];v!=start;v=u,u=pre[u]){

                            maze[u][v]-=aug;

                            maze[v][u]+=aug;

                        }

                        aug=-;

                    }

                    goto loop;

                }

            int mindis=nodenum-;

            for(int v=;v<nodenum;v++)

                if(maze[u][v]&&mindis>dis[v]){

                    cur[u]=v;

                    mindis=dis[v];

                }

            if((--gap[dis[u]])==)break;

            gap[dis[u]=mindis+]++;

            u=pre[u];

    }

    return maxflow;

}

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        memset(maze,,sizeof(maze));

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            maze[u][v]=z;

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            maze[sp][u]=z;

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            maze[u][sc]=z;

        }

        printf("%d\n",sap(sp,sc,n));

    }

    return ;

}

2、SAP邻接矩阵形式2：

/*

保留原矩阵，可用于多次使用最大流

SAP邻接矩阵形式

点的编号从0开始

增加个flow数组，保留原矩阵maze，可用于多次使用最大流

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;

int maze[MAXN][MAXN];

int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];

int flow[MAXN][MAXN];//存最大流的容量

int sap(int start,int end,int nodenum){

    memset(cur,,sizeof(cur));

    memset(dis,,sizeof(dis));

    memset(gap,,sizeof(gap));

    memset(flow,,sizeof(flow));

    int u=pre[start]=start,maxflow=,aug=-;

    gap[]=nodenum;

    while(dis[start]<nodenum){

        loop:

            for(int v=cur[u];v<nodenum;v++)

                if(maze[u][v]-flow[u][v]&&dis[u]==dis[v]+){

                    if(aug==-||aug>maze[u][v]-flow[u][v])aug=maze[u][v]-flow[u][v];

                    pre[v]=u;

                    u=cur[u]=v;

                    if(v==end){

                        maxflow+=aug;

                        for(u=pre[u];v!=start;v=u,u=pre[u]){

                            flow[u][v]+=aug;

                            flow[v][u]-=aug;

                        }

                        aug=-;

                    }

                    goto loop;

                }

            int mindis=nodenum-;

            for(int v=;v<nodenum;v++)

            if(maze[u][v]-flow[u][v]&&mindis>dis[v]){

                cur[u]=v;

                mindis=dis[v];

            }

            if((--gap[dis[u]])==)break;

            gap[dis[u]=mindis+]++;

            u=pre[u];

    }

    return maxflow;

}

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        memset(maze,,sizeof(maze));

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            maze[u][v]=z;

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            maze[sp][u]=z;

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            maze[u][sc]=z;

        }

        printf("%d\n",sap(sp,sc,n));

    }

    return ;

}

3、ISAP邻接表形式：注意一下边数的范围

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;//点数的最大值

const int MAXM=;//边数的最大值（加的双向加，所以是2倍，别忘了加上超级源点和超级汇点（共400条））

const int INF=0x3f3f3f3f;

struct Edge{

    int to,next,cap,flow;

}edge[MAXM];//注意是MAXM

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];

void init(){

    tol=;

    memset(head,-,sizeof(head));

}

//加边，单向图三个参数，双向图四个参数

void addedge(int u,int v,int w,int rw=){

    edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];

    edge[tol].flow=;head[u]=tol++;

    edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];

    edge[tol].flow=;head[v]=tol++;

}

//输入参数：起点、终点、点的总数

//点的编号没有影响，只要输入点的总数

int sap(int start,int end,int N){

    memset(gap,,sizeof(gap));

    memset(dep,,sizeof(dep));

    memcpy(cur,head,sizeof(head));

    int u=start;

    pre[u]=-;

    gap[]=N;

    int ans=;

    while(dep[start]<N){

        if(u==end){

            int Min=INF;

            for(int i=pre[u];i!=-;i=pre[edge[i^].to])

                if(Min>edge[i].cap-edge[i].flow)

                    Min=edge[i].cap-edge[i].flow;

            for(int i=pre[u];i!=-;i=pre[edge[i^].to]){

                edge[i].flow+=Min;

                edge[i^].flow-=Min;

            }

            u=start;

            ans+=Min;

            continue;

        }

        bool flag=false;

        int v;

        for(int i=cur[u];i!=-;i=edge[i].next){

            v=edge[i].to;

            if(edge[i].cap-edge[i].flow&&dep[v]+==dep[u]){

                flag=true;

                cur[u]=pre[v]=i;

                break;

            }

        }

        if(flag){

            u=v;

            continue;

        }

        int Min=N;

        for(int i=head[u];i!=-;i=edge[i].next)

            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){

                Min=dep[edge[i].to];

                cur[u]=i;

            }

        gap[dep[u]]--;

        if(!gap[dep[u]])return ans;

        dep[u]=Min+;

        gap[dep[u]]++;

        if(u!=start)u=edge[pre[u]^].to;

    }

    return ans;

}

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        init();

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            addedge(u,v,z);

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(sp,u,z);

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(u,sc,z);

        }

        printf("%d\n",sap(sp,sc,n));

    }

    return ;

}

4、ISAP+bfs初始化+栈优化：注意一下边数的范围

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;//点数的最大值

const int MAXM=;//边数的最大值

const int INF=0x3f3f3f3f;

struct Edge{

    int to,next,cap,flow;

}edge[MAXM];//注意是MAXM

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],cur[MAXN];

void init(){

    tol=;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int w,int rw=){

    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=;

    edge[tol].next=head[u];head[u]=tol++;

    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=;

    edge[tol].next=head[v];head[v]=tol++;

}

int Q[MAXN];

void BFS(int start,int end){

    memset(dep,-,sizeof(dep));

    memset(gap,,sizeof(gap));

    gap[]=;

    int front=,rear=;

    dep[end]=;

    Q[rear++]=end;

    while(front!=rear){

        int u=Q[front++];

        for(int i=head[u];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(dep[v]!=-)continue;

            Q[rear++]=v;

            dep[v]=dep[u]+;

            gap[dep[v]]++;

        }

    }

}

int S[MAXN];

int sap(int start,int end,int N){

    BFS(start,end);

    memcpy(cur,head,sizeof(head));

    int top=;

    int u=start;

    int ans=;

    while(dep[start]<N){

        if(u==end){

            int Min=INF;

            int inser;

            for(int i=;i<top;i++)

                if(Min>edge[S[i]].cap-edge[S[i]].flow){

                    Min=edge[S[i]].cap-edge[S[i]].flow;

                    inser=i;

                }

            for(int i=;i<top;i++){

                edge[S[i]].flow+=Min;

                edge[S[i]^].flow-=Min;

            }

            ans+=Min;

            top=inser;

            u=edge[S[top]^].to;

            continue;

        }

        bool flag=false;

        int v;

        for(int i=cur[u];i!=-;i=edge[i].next){

            v=edge[i].to;

            if(edge[i].cap-edge[i].flow&&dep[v]+==dep[u]){

                flag=true;

                cur[u]=i;

                break;

            }

        }

        if(flag){

            S[top++]=cur[u];

            u=v;

            continue;

        }

        int Min=N;

        for(int i=head[u];i!=-;i=edge[i].next)

            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){

                Min=dep[edge[i].to];

                cur[u]=i;

            }

        gap[dep[u]]--;

        if(!gap[dep[u]])return ans;

        dep[u]=Min+;

        gap[dep[u]]++;

        if(u!=start)u=edge[S[--top]^].to;

    }

    return ans;

}

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        init();

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            addedge(u,v,z);

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(sp,u,z);

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(u,sc,z);

        }

        printf("%d\n",sap(sp,sc,n));

    }

    return ;

}

5、dinic：注意一下边数的范围

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;//点数的最大值

const int MAXM=;//边数的最大值

const int INF=0x3f3f3f3f;

struct Edge{

    int to,next,cap,flow;

}edge[MAXM];//注意是MAXM

int tol;

int head[MAXN];

void init(){

    tol=;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int w,int rw=){

    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=;

    edge[tol].next=head[u];head[u]=tol++;

    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=;

    edge[tol].next=head[v];head[v]=tol++;

}

int Q[MAXN];

int dep[MAXN],cur[MAXN],sta[MAXN];

bool bfs(int s,int t,int n){

    int front=,tail=;

    memset(dep,-,sizeof(dep[])*(n+));

    dep[s]=;

    Q[tail++]=s;

    while(front<tail){

        int u=Q[front++];

        for(int i=head[u];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(edge[i].cap>edge[i].flow&&dep[v]==-){

                dep[v]=dep[u]+;

                if(v==t)return true;

                Q[tail++]=v;

            }

        }

    }

    return false;

}

int dinic(int s,int t,int n){

    int maxflow=;

    while(bfs(s,t,n)){

        for(int i=;i<n;i++)cur[i]=head[i];

        int u=s,tail=;

        while(cur[s]!=-){

            if(u==t){

                int tp=INF;

                for(int i=tail-;i>=;i--)

                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);

                maxflow+=tp;

                for(int i=tail-;i>=;i--){

                    edge[sta[i]].flow+=tp;

                    edge[sta[i]^].flow-=tp;

                    if(edge[sta[i]].cap-edge[sta[i]].flow==)

                        tail=i;

                }

                u=edge[sta[tail]^].to;

            }

            else if(cur[u]!=-&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+==dep[edge[cur[u]].to]){

                sta[tail++]=cur[u];

                u=edge[cur[u]].to;

            }

            else{

                while(u!=s&&cur[u]==-)

                    u=edge[sta[--tail]^].to;

                cur[u]=edge[cur[u]].next;

            }

        }

    }

    return maxflow;

}

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        init();

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            addedge(u,v,z);

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(sp,u,z);

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            addedge(u,sc,z);

        }

        printf("%d\n",dinic(sp,sc,n));

    }

    return ;

}

以上算法均取自kuangbin模板，ac时间均不到100ms。

下面补上一个增广路算法（EdmondsKarp算法），但是时间让人捉急，1000多ms

6、增广路算法（EdmondsKarp算法）：

#include<iostream>

#include<stdio.h>

#include<vector>

#include<string.h>

#include<queue>

using namespace std;

const int maxn=;

const int INF=0x3f3f3f3f;

struct Edge{

    int from,to,cap,flow;

    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}

};

struct EdmondsKarp{

    int n,m;//n好像没用到

    vector<Edge>edges;//边数的两倍

    vector<int>G[maxn];//邻接表，G[i][j]表示结点i的第j条边在e数组中的序号

    int a[maxn];//当起点到i的可改进量

    int p[maxn];//最短路树上p的入弧编号

    void init(int n){

        for(int i=;i<n;i++)G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap){

        edges.push_back(Edge(from,to,cap,));

        edges.push_back(Edge(to,from,,));//反向弧

        m=edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    int Maxflow(int s,int t){

        int flow=;

        for(;;){

            memset(a,,sizeof(a));

            queue<int>Q;

            Q.push(s);

            a[s]=INF;

            while(!Q.empty()){

                int x=Q.front();Q.pop();

                for(int i=;i<G[x].size();i++){

                    Edge &e=edges[G[x][i]];

                    if(!a[e.to]&&e.cap>e.flow){

                        p[e.to]=G[x][i];

                        a[e.to]=min(a[x],e.cap-e.flow);

                        Q.push(e.to);

                    }

                }

                if(a[t])break;

            }

            if(!a[t])break;

            for(int u=t;u!=s;u=edges[p[u]].from){

                edges[p[u]].flow+=a[t];

                edges[p[u]^].flow-=a[t];

            }

            flow+=a[t];

        }

        return flow;

    }

}EK;

int main(){

    int n,np,nc,m;//节点总数，源点，汇点，边数

    int u,v,z;//节点u，节点v，最大流量z

    char str[];//处理空格

    int sp,sc;//超级源点，超级汇点

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){

        EK.init(n+);//加上下面增加的超级源点和超级汇点

        for(int i=;i<m;++i){

            scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z);

            EK.AddEdge(u,v,z);

        }

        //建立超级源点

        sp=n++;

        for(int i=;i<np;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            EK.AddEdge(sp,u,z);

        }

        //建立超级汇点

        sc=n++;

        for(int i=;i<nc;++i){

            scanf("%1s%d%1s%d",str,&u,str,&z);

            EK.AddEdge(u,sc,z);

        }

        printf("%d\n",EK.Maxflow(sp,sc));

    }

    return ;

}

巴特西

POJ - 1459 Power Network（最大流）（模板）

最新文章

热门文章