網絡流相關算法總結,最大流EK算法,SAP算法,最小費用最大流,最小費用路算法,最大流最小割定理 -开发者知识库

網絡流相關算法總結,最大流EK算法,SAP算法,最小費用最大流,最小費用路算法,最大流最小割定理 -开发者知识库,第1张

網絡流相關定義

  1. 網絡是一個有向帶權圖,包含一個源點和一個匯點,沒反平行邊
  2. 網絡流:即網絡上的流,是定義在邊集E上的一個非負函數 flow={flow(u,v)} , flow(u,v) 是邊上的流量
  3. 可行流:滿足容量約束流量守恆的網絡流
  4. 網絡最大流:滿足容量約束流量守恆的條件下,在流網絡中找到一個凈輸出最大的網絡流

最大流

求解最大流的整體思路是福特福克森算法。該算法的思想是:
在殘余網絡中找可增廣路,然后在實流網絡中沿着可增廣路增流,在殘余網絡中沿着可增廣路減流,;繼續在殘余網絡中找可增廣路。直到不存在可增廣路位置。此時,實流網絡中的可行流就是所求的最大流.

增廣路定理:設 flow 是網絡 G 的一個可行流,如果不存在從源點 S 到匯點 t 關於 flow 的可增廣路 p ,則 flow G 的一個最大流

福特福克森也是能算是一種求解最大流的思想,並不是具體的算法。下面說一下具體實現的算法。
實現的算法有三種:EK算法,Dinic算法,SAP算法 gap優化

我說一下EK算法和SAP算法。

EK算法

鄰接矩陣存儲殘余網絡,利用一個隊列q來存放已訪問未檢查的點,vis[]數組來標記當前點是否被訪問過,pre[]數組來記錄前驅節點。

利用BFS來尋找可增廣路,當存在一條可增廣路時。從匯點一直往前面找,一直找到起點,在路徑上找到一條可增廣量最小的邊,然后從起點到匯點,殘余網絡中正向沿着可增廣路增流,反向沿着可增廣路減流,然后不斷地進行BFS,把每一次的可增光量累加起來,就是最大流

復雜度: O(VE2)

代碼:
可以AC:POJ1273 Drainage Ditches(網絡流–最大流,EK增廣路算法)

#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const int N=200 20;
int g[N][N],f[N][N],pre[N];//分別代表殘余網絡,實流網絡,前驅數組
bool vis[N];//標記數組
int n,m;//點數和邊數
bool bfs(int s,int t)
{
    mem(pre,-1);
    mem(vis,false);
    queue<int>q;
    vis[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=1; i<=n; i  )
        {
            if(!vis[i]&&g[now][i]>0)
            {
                vis[i]=true;
                pre[i]=now;
                if(i==t)
                    return true;
                q.push(i);
            }
        }
    }
    return false;
}
int EK(int s,int t)
{
    int v,w,d,maxflow=0;
    while(bfs(s,t))
    {
        v=t;
        d=inf;
        while(v!=s)
        {
            w=pre[v];
            d=min(d,g[w][v]);
            v=w;
        }
        maxflow =d;
        v=t;
        while(v!=s)
        {
            w=pre[v];
            g[w][v]-=d;
            g[v][w] =d;
            if(f[v][w]>0)
                f[v][w]-=d;
            else
                f[w][v] =d;
            v=w;
        }
    }
    return maxflow;
}
int main()
{
    int a,b,c;
    while(~scanf("%d%d",&m,&n))
    {
        mem(g,0);
        mem(f,0);
        for(int i=1; i<=m; i  )
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a][b] =c;
        }
        printf("%d\n",EK(1,n));
    }
    return 0;
}

SAP重貼標簽算法

在這個算法中,我們用鄰接表存儲混合網絡(正向邊顯示,cap,flow,反向邊也顯示這個).

這個算法的思想是,我們給廣搜的網絡標一個高度,每一層一個高度,最后一層的高度是0,然后按照廣搜的層次,到起點依次遞增。然后搜索的時候直接按照標簽的告訴從高到低找,這樣可以加快效率,當走的點的標簽高度走不動的時候,我們采取重貼標簽的策略,令當前節點的高度=所有鄰接點高度的最小值 1,如果沒有鄰接邊,則令當前節點的高度=節點數(注意:一定要保證容量>流量),然后不斷的進行貼標簽,重貼標簽的過程,累積可增廣量,最后的值就是最大流

我們需要進行gap優化:利用一個數組g[]來記錄,當前的高度的節點有多少個,當重貼標簽后發現當前高度的點只有一個那么就可以提前結束程序

算法復雜度: O(V2E)

下面是代碼:
可以AC: P3376 【模板】網絡最大流

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const int N=10000 20;
const int M=100000 20;
int top;
int h[N],pre[N],g[N];//h[i]記錄每個節點的高度,pre[i]記錄前驅,g[i]表示距離為i個節點數有多少個
int first[N];
struct node
{
    int v,next;
    int cap,flow;
} E[M*2];
void init()
{
    mem(first,-1);
    top=0;
}
void add_edge(int u,int v,int c)
{
    E[top].v=v;
    E[top].cap=c;
    E[top].flow=0;
    E[top].next=first[u];
    first[u]=top  ;
}
void add(int u,int v,int c)
{
    add_edge(u,v,c);
    add_edge(v,u,0);
}

void set_h(int t)//標高函數,從終點向起點標高
{
    queue<int>q;
    mem(h,-1);
    mem(g,0);
    h[t]=0;
    q.push(t);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        g[h[v]]  ;//當前高度的個數 1
        for(int i=first[v]; ~i; i=E[i].next)
        {
            int u=E[i].v;
            if(h[u]==-1)//當前節點未標高
            {
                h[u]=h[v] 1;
                q.push(u);
            }
        }
    }
}

int Isap(int s,int t,int n)//isap算法
{
    set_h(t);
    int ans=0,u=s;
    int d;
    while(h[s]<n)//節點的高度小於頂點數
    {
        int i=first[u];
        if(u==s) d=inf;
        for(; ~i; i=E[i].next)
        {
            int v=E[i].v;
            if(E[i].cap>E[i].flow&&h[u]==h[v] 1)//容量大於流量且當前的高度等於要去的高度 1
            {
                u=v;
                pre[v]=i;
                d=min(d,E[i].cap-E[i].flow);//找最小增量
                if(u==t)//到達匯點
                {
                    while(u!=s)
                    {
                        int j=pre[u];//找到u的前驅
                        E[j].flow =d;//正向流量 d
                        E[j^1].flow-=d;//反向流量-d
                        u=E[j^1].v;//向前搜索
                    }
                    ans =d;
                    d=inf;
                }
                break;
            }
        }
        if(i==-1)//鄰接邊搜索完畢,無法行進
        {
            if(--g[h[u]]==0)//重要的優化,這個高度的節點只有一個,結束
                break;
            int hmin=n-1;//重貼標簽的高度初始為最大
            for(int j=first[u]; ~j; j=E[j].next)
            {
                if(E[j].cap>E[j].flow)
                    hmin=min(hmin,h[E[j].v]);//取所有鄰接點高度的最小值
            }
            h[u]=hmin 1;//重新標高
            g[h[u]]  ;//標高后該高度的點數 1
            if(u!=s)//不是源點時,向前退一步,重新搜
                u=E[pre[u]^1].v;
        }
    }
    return ans;
}
int main()
{
    int n,m,u,v,w,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init();
    for(int i=1; i<=m; i  )
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    printf("%d\n",Isap(s,t,n));
    return 0;
}

kuangbin的SAP模板

const int N=1000 20;
const int M=2*100000 20;
int top;
int h[N],pre[N],g[N],first[N],cur[N];//h[i]記錄每個節點的高度,pre[i]記錄前驅,g[i]表示距離為i個節點數有多少個
struct node
{
    int v,next,cap;
} E[M];
void init()
{
    mem(first,-1);
    top=0;
}
void add_edge(int u,int v,int c)
{
    E[top].v=v;
    E[top].cap=c;
    E[top].next=first[u];
    first[u]=top  ;
    E[top].v=u;
    E[top].cap=0;
    E[top].next=first[v];
    first[v]=top  ;
}
int sap(int start,int end,int nodenum)
{
    memset(h,0,sizeof(h));
    memset(g,0,sizeof(g));
    memcpy(cur,first,sizeof(first));
    int u=pre[start]=start,maxflow=0,aug=-1;
    g[0]=nodenum;
    while(h[start]<nodenum)
    {
loop:
        for(int &i=cur[u]; i!=-1; i=E[i].next)
        {
            int v=E[i].v;
            if(E[i].cap&&h[u]==h[v] 1)
            {
                if(aug==-1||aug>E[i].cap)
                    aug=E[i].cap;
                pre[v]=u;
                u=v;
                if(v==end)
                {
                    maxflow =aug;
                    for(u=pre[u]; v!=start; v=u,u=pre[u])
                    {
                        E[cur[u]].cap-=aug;
                        E[cur[u]^1].cap =aug;
                    }
                    aug=-1;
                }
                goto loop;
            }
        }
        int mindis=nodenum;
        for(int i=first[u]; i!=-1; i=E[i].next)
        {
            int v=E[i].v;
            if(E[i].cap&&mindis>h[v])
            {
                cur[u]=i;
                mindis=h[v];
            }
        }
        if((--g[h[u]])==0)break;
        g[h[u]=mindis 1]  ;
        u=pre[u];
    }
    return maxflow;
}

最小費用最大流

在求最大流的過程中,對於每一條邊都有一個費用,現在希望費用最小,流最大。求最大流和最小費用。

最小費用路算法

最小費用路算法的思想是:先找最小費用路,在該路徑上面增流,增加到最大流。

利用鄰接表建立雙向邊,正向邊的花費為cost,反向邊的花費為-cost.
在找最小費用路的時候,從源點出發,沿着可行 (E[i].cap>E[i].flow)廣度搜索每個鄰接點, 如果當前的邊可以繼續松弛,那么就更新,就是SPFA算法,並且記錄一下前驅。

當找到最小費用路以后,那么就從匯點向源點找一條,最小的可增流量,沿着增廣路正向增流,反向減流,最后花費的費用為:

mincost=dis[V]d

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复