网络流模板（更新中）-白红宇

网络流模板（更新中）

阅读量：4332 次

发布时间：2019-06-06

本文共 9697 字，大约阅读时间需要 32 分钟。

最大流：

性质：1. f(u,v)= - f(v,u) 2.流量守恒（即每一个非源点s，非汇点t的点流入量=流出量）

3.源点的流出量=汇点的流入量4.最小割=最大流（C(S,T)：两个点集之间边的最小容量和）

最大流共同的思想：先找增广流路径，再更新该路径上的边的残流（剩余流量）。

/*最大流EK算法，O(V*E*E)算法思想：先找到一条可流的增广路P，再把P中的边的最小残余量增加最在流中。更新残余量。

*/ #include<stdio.h> #include<string.h> #include<queue> using namespace std; #define captype __int64 const int N = 205; captype cap[N][N],f[N][N],rest[N]; int sNode,eNode,pre[N]; void init(){ memset(f,0,sizeof(f)); memset(cap,0,sizeof(cap)); } bool searchPath(int n){//找一条增广路 bool vist[N]={0}; queue<int>q; int u,v; u=sNode; vist[u]=1; pre[u]=u; rest[u]=1<<30; q.push(u); while(!q.empty()){ u=q.front(); q.pop(); for(v=1; v<=n; v++) if(!vist[v]&&cap[u][v]-f[u][v]>0) { vist[v]=1; pre[v]=u; if(cap[u][v]-f[u][v]>rest[u]) rest[v]=rest[u]; else rest[v]=cap[u][v]-f[u][v]; if(v==eNode) return true; q.push(v); } } return false; } captype maxflow(int s,int t,int n){ captype ans=0; sNode=s; eNode=t; while(searchPath(n)){ ans+=rest[eNode]; int v=eNode; while(v!=sNode){ int u=pre[v]; f[u][v]+=rest[eNode]; f[v][u]-=rest[eNode];//给一个回流的机会 v=u; } } return ans; } int main(){ int a,b,c; while(~scanf("%d%d",&n,&m)){ scanf("%d%d",&sNode,&eNode); init(); while(m--){ scanf("%d%d%d",&a,&b,&c); cap[a][b]+=c; } printf("%d\n",maxflow(sNode,eNode,n)); } }

/*最大流：压入重标记push_relabel算法O(VE)算法思想：从高流向低。尽量把通道注满,活节点(即顶点有流量)的高度在不断的变存图：邻接表法*/#include
     
      #include
      
       #include
       
        using namespace std;#define captype __int64const int N  = 210;const int MAX= 1<<30;struct EDG{    int to,nxt;    captype c;  //每条边的残留量}edg[N*N];int head[N],eid;captype vf[N];     //顶点的剩余流量int h[N];      //顶点的高度//int n;         //顶点个总个数，包括源点与汇点int min(int a,int b){return a>b?b:a; }void init(){    memset(head,-1,sizeof(head));    eid=0;}//加入 有向边void addEdg(int u , int v, captype c){    edg[eid].to=v; edg[eid].nxt=head[u]; edg[eid].c=c; head[u]=eid++;    edg[eid].to=u; edg[eid].nxt=head[v]; edg[eid].c=0; head[v]=eid++;}captype maxFlow(int sNode,int eNode,int n){//源点与汇点，注意：n为点的总个数,包括源点与汇点    captype ans=0;    queue
        
         q;    memset(h,0,sizeof(h));    memset(vf,0,sizeof(vf));    h[sNode]=n+1;   //源点的高度    vf[sNode]=MAX;  //源点的余流    q.push(sNode);    while(!q.empty()){        int u=q.front(); q.pop();        int minh=MAX;        for(int i=head[u]; i!=-1; i=edg[i].nxt){            int v=edg[i].to;            captype fp;            if(edg[i].c
         
          0 ){                minh=min(minh, h[v]);                if(u==sNode || h[u]==h[v]+1){                    edg[i].c-=fp;                    edg[i^1].c+=fp; //反向边，给个反回的通道                    vf[u]-=fp;                    vf[v]+=fp;                    if(v==eNode) ans+=fp;   //当到达汇点时。就加入最大流中                    if(v!=sNode && v!=eNode )   //仅仅有即不是源点，也不是汇点时才干进队列                        q.push(v);                }            }            if(vf[u]==0) break; //假设顶点的余流为0，则能够跳出for循环        }        //假设不是源点（也非汇点）。且顶点仍有余流，则又一次标记 高度+1 入队        //这里赋值为最低的相邻顶点的高度高一个单位,也能够简单的在原高度+1        if(u!=sNode && vf[u]>0){            h[u] = minh + 1;            q.push(u);        }    }    return ans;}

/*最大流：SAP算法。与ISAP的区别就是不用预处理*/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define captype intconst int MAXN = 100010;   //点的总数const int MAXM = 400010;    //边的总数const int INF = 1<<30;struct EDG{    int to,next;    captype cap,flow;} edg[MAXM];int eid,head[MAXN];int gap[MAXN];  //每种距离(或可觉得是高度)点的个数int dis[MAXN];  //每一个点到终点eNode 的最短距离int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边int pre[MAXN];void init(){    eid=0;    memset(head,-1,sizeof(head));}//有向边 三个參数。无向边4个參数void addEdg(int u,int v,captype c,captype rc=0){    edg[eid].to=v; edg[eid].next=head[u];    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;    edg[eid].to=u; edg[eid].next=head[v];    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;}captype maxFlow_sap(int sNode,int eNode, int n){//n是包含源点和汇点的总点个数。这个一定要注意    memset(gap,0,sizeof(gap));    memset(dis,0,sizeof(dis));    memcpy(cur,head,sizeof(head));    pre[sNode] = -1;    gap[0]=n;    captype ans=0;  //最大流    int u=sNode;    while(dis[sNode]
         
          edg[i].cap-edg[i].flow){                Min=edg[i].cap-edg[i].flow;                inser=i;            }            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){                edg[i].flow+=Min;                edg[i^1].flow-=Min;  //可回流的边的流量            }            ans+=Min;            u=edg[inser^1].to;            continue;        }        bool flag = false;  //推断是否能从u点出发可往相邻点流        int v;        for(int i=cur[u]; i!=-1; i=edg[i].next){            v=edg[i].to;            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){                flag=true;                cur[u]=pre[v]=i;                break;            }        }        if(flag){            u=v;            continue;        }        //假设上面没有找到一个可流的相邻点，则改变出发点u的距离（也可觉得是高度）为相邻可流点的最小距离+1        int Mind= n;        for(int i=head[u]; i!=-1; i=edg[i].next)        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){            Mind=dis[edg[i].to];            cur[u]=i;        }        gap[dis[u]]--;        if(gap[dis[u]]==0) return ans;  //当dis[u]这样的距离的点没有了。也就不可能从源点出发找到一条增广流路径                                        //由于汇点到当前点的距离仅仅有一种，那么从源点到汇点必定经过当前点，然而当前点又没能找到可流向的点，那么必定断流        dis[u]=Mind+1;//假设找到一个可流的相邻点。则距离为相邻点距离+1。假设找不到。则为n+1        gap[dis[u]]++;        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边    }    return ans;}

/*最大流：ISAP+BFS  初始化+栈优化算法思想：先预处理汇点到全部点的最短距离，并记录每种距离点的个数（用于优化），在从源点寻找增广流路径时用栈优化，            用栈的优点是：当找到一条可增流的路时。在流的瓶颈边处裁断。在栈中它的下方边还是能够增流。反复利用，            若没找到能够退出一条边。继续找。存图：邻接表*/#include
     
      #include
      
       #include
       
        using namespace std;#define captype __int64  const int MAXN = 100010;   //点的总数const int MAXM = 400010;    //边的总数const int INF = 1<<30;struct EDG{    int to,next;    captype cap,flow;} edg[MAXM];int eid,head[MAXN];int gap[MAXN];  //每种距离(或可觉得是高度)点的个数int dis[MAXN];  //每一个点到终点eNode 的最短距离int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边void init(){    eid=0;    memset(head,-1,sizeof(head));}//有向边 三个參数，无向边4个參数void addEdg(int u,int v,captype c,captype rc=0){    edg[eid].to=v; edg[eid].next=head[u];    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;    edg[eid].to=u; edg[eid].next=head[v];    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;}//预处理eNode点到全部点的最短距离void BFS(int sNode, int eNode){    queue
        
         q;    memset(gap,0,sizeof(gap));    memset(dis,-1,sizeof(dis));    gap[0]=1;    dis[eNode]=0;    q.push(eNode);    while(!q.empty()){        int u=q.front(); q.pop();        for(int i=head[u]; i!=-1; i=edg[i].next){            int v=edg[i].to;            if(dis[v]==-1){                dis[v]=dis[u]+1;                gap[dis[v]]++;                q.push(v);            }        }    }}int S[MAXN];    //路径栈。存的是边的id号captype maxFlow_sap(int sNode,int eNode, int n){  //注意：n为点的总个数。包含源点与汇点    BFS(sNode, eNode);              //预处理eNode到全部点的最短距离    if(dis[sNode]==-1) return 0;    //源点到不可到达汇点    memcpy(cur,head,sizeof(head));    int top=0;  //栈顶    captype ans=0;  //最大流    int u=sNode;    while(dis[sNode]
         
          edg[S[i]].cap-edg[S[i]].flow){                Min=edg[S[i]].cap-edg[S[i]].flow;                inser=i;            }            for(int i=0; i
          
           0 && dis[u]==dis[v]+1){ flag=true; cur[u]=i; break; } } if(flag){ S[top++] = cur[u]; //增加一条边 u=v; continue; } //假设上面没有找到一个可流的相邻点。则改变出发点u的距离（也可觉得是高度）为相邻可流点的最小距离+1 int Mind= n; for(int i=head[u]; i!=-1; i=edg[i].next) if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){ Mind=dis[edg[i].to]; cur[u]=i; } gap[dis[u]]--; if(gap[dis[u]]==0) return ans; //当dis[u]这样的距离的点没有了。也就不可能从源点出发找到一条增广流路径 //由于汇点到当前点的距离仅仅有一种，那么从源点到汇点必定经过当前点，然而当前点又没能找到可流向的点，那么必定断流 dis[u]=Mind+1; //假设找到一个可流的相邻点。则距离为相邻点距离+1，假设找不到。则为n+1 gap[dis[u]]++; if(u!=sNode) u=edg[S[--top]^1].to; //退一条边 } return ans;}

最小费用最大流：

/*最小费用最大流：求最大费用仅仅需费用cost取反，结果取反就可以。算法思想：先用spfa找一条最小费用的可增广流路径。再更新残流网络，数组模拟队列快存图：邻接表*/#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 10010;const int MAXM = 100100;const int INF = 1<<30;struct EDG{    int to,next,cap,flow;    int cost;  //单位价格}edg[MAXM];int head[MAXN],eid;int pre[MAXN], cost[MAXN] ; //点0~(n-1)void init(){    eid=0;    memset(head,-1,sizeof(head));}void addEdg(int u,int v,int cap,int cst){    edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;    edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++;    edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;    edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++;}bool inq[MAXN];int q[MAXN];bool spfa(int sNode,int eNode,int n){    int l=0 , r=0;    for(int i=0; i
        
         0 && cost[v]>cost[u]+edg[i].cost){ //在满足可增流的情况下。最小花费                cost[v] = cost[u]+edg[i].cost;                pre[v]=i;   //记录路径上的边                if(!inq[v]){                    if(r==MAXN)r=0;                    q[r++]=v;                    inq[v]=1;                }            }        }    }    return cost[eNode]!=INF;    //推断有没有增广路}//反回的是最大流，最小花费为minCostint minCost_maxFlow(int sNode,int eNode ,int& minCost,int n){    int ans=0;    while(spfa(sNode,eNode,n)){        int mint=INF;        for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){            if(mint>edg[i].cap-edg[i].flow)                mint=edg[i].cap-edg[i].flow;        }        ans+=mint;        for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){            edg[i].flow+=mint; edg[i^1].flow-=mint;            minCost+=mint*edg[i].cost;        }    }    return ans;}int main(){    //输入。初始化init()}

转载于:https://www.cnblogs.com/liguangsunls/p/7294145.html

你可能感兴趣的文章