【ネットワークフロー関連】最大フローと費用フローのEKアルゴリズム実装

Luogu P 3376最大ストリームはネットワークストリームモデルの基礎的な問題である.ネットワークストリームモデルは特殊な有向図である.コンセプト:

源点:流のノードを提供し、類比は無限放水の水場

となる.

合流点:流れを受け入れるノードであり、類比は無限に水を受け取るセル

となる.

弧:類比は水道管

アークの容量:類比は水道管の容量である.関数(c(x,y))で弧((x,y))を表す容量

アークの流量:類比は現在の水道管中の水の量である.関数(f(x,y))で弧((x,y))を表す流量

アークの残量:すなわち容量-流量

容量ネットワーク:1つのネットワークストリームモデルに対して、各アークに容量が与えられると、1つの容量ネットワークが構成される.

トラフィックネットワーク:1つのネットワークストリームモデルに対して、各アークがトラフィックを与え、1つのトラフィックネットワークを構成する.

残量ネットワーク:1つのネットワークストリームモデルに対して、各アークに残量が与えられると、1つの残量ネットワークが構成される.最初の残量ネットワークは容量ネットワークである.

ネットワークフローモデル(G=(V,E))((V)はポイントセット、(E)はエッジセット)には次のような性質があります.

流量保存:ソースポイントとシンクポイントを除いて、任意のノードに流入するストリームは、ノードから流出するストリーム

に等しいに違いない.

容量制限(forall(x,y)in E、0<=f(x,y)<=c(x,y))

斜対称性(forall(x,y)in E、f(x,y)=-f(y,x).)関数パリティの奇数関数、またはベクトルの方向に似ています.

最大流問題は,ソース点SからポイントTまでの輸送流量を通俗的に解釈し,最大どれだけの流量がポイントに輸送できるかを尋ねる.このような問題に対して、私たちはいくつかの新しい概念を導入しました.

拡張パス:ソースポイントからポイントへのパス(R)、満足(forall(x,y)in S,c(x,y)-f(x,y)>=0.)すなわち残量非負

最大ストリーム最小分割の定理:ネットワークストリームモデルは最大ストリームに達し、残量ネットワークに増幅路がない場合(不完全であるが十分である)

のみである.
(Ford-Fulkerson)メソッド:毎回拡張パスを探します.バケツ原理によれば、この増幅路の最大流量(f_{max}<=min(c(x,y)−f(x,y))である.これにより、ソースポイントからパケットポイントにトラフィックが送信され、パス上のすべてのアークの残量が拡張パスが見つからないまで変更されます.(Edmons-Karp)アルゴリズム:(Ford-Fulkerson)メソッドに基づくアルゴリズムで、コアは(BFS)を利用してソースポイントから集約ポイントへの最短拡張路を検索し、(Ford-Fulkerson)メソッドに基づいて残量ネットワークを修正することである.複雑度が最悪である(O(nm^2))なので,実際には最大ストリームに関する問題を求める際には,残量ネットワークのみを利用しており,トラフィックや容量は一般的に記録する必要はない.キー:最大ストリームを求めるときにエッジのトラフィックを削減する必要がある場合があるため、逆エッジを導入しました.逆エッジを選択すると、順エッジの流量を削減することに相当します.リバースエッジの残量が順方向エッジの流量(最大で順方向流量を適切に相殺する)に等しいことが容易に見出され、アルゴリズムの正確性が保証される.

#include
#include
#include
#include
using namespace std;
struct data
{
    int to,next,val;
}e[2*100005];
int cnt,head[10005],prep[10005],pree[10005],flow[10005],ans;
queue que;
int n,m,s,t,u,v,w;
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].val=w;
}
int bfs(int s,int t)
{
    while (!que.empty()) que.pop();
    flow[s]=0x3f3f3f3f;//flow                
    que.push(s);
    for (int i=1;i<=n;i++) 
    {
        prep[i]=-1;//        
        pree[i]=0;//          
    }
    prep[s]=0;
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        if (now==t) break;
        for (int i=head[now];i;i=e[i].next)
        {
            if (e[i].val>0&&prep[e[i].to]==-1)
            {
                que.push(e[i].to);
                flow[e[i].to]=min(flow[now],e[i].val);
                pree[e[i].to]=i;
                prep[e[i].to]=now;
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
void EK(int s,int t)
{
    int delta=bfs(s,t);//            
    while (delta!=-1)
    {
        ans+=delta;
        for (int j=t;j;j=prep[j])
        {
            e[pree[j]].val-=delta;
            e[pree[j]^1].val+=delta;
            //          2          1          。
        }
        delta=bfs(s,t);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    cnt=1;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,0);
        add(u,v,w);
        //     
    }
    EK(s,t);
    printf("%d",ans);
    return 0;
}

Luogu P 3381は、現在、各アークに1つの費用を加えていると仮定し、そのアーク単位流量に必要な費用を表し、最小費用最大流を要求する.では、これが費用の流れの問題です.実際には難しくないが,EKアルゴリズムを少し修正し,EKにおけるBFSの最短拡張路をSPFAに変更して最小費用の拡張路を探せばよい

#include
#include
using namespace std;
const int maxn=5005,maxm=50005,inf=0x3f3f3f3f;
struct data
{
    int to,next,val,pri;
}e[2*maxm];
int cnt,tot,ans,head[maxn],n,m,s,t,u,v,w,f,cost[maxn],prep[maxn],pree[maxn],flow[maxn];
void add(int u,int v,int w,int f)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].val=w;
    e[cnt].pri=f;
    head[u]=cnt;
}
queue que; 
int vis[maxn];
int SPFA(int s,int t)
{
    for (int i=1;i<=n;i++) 
    {
        cost[i]=inf;
        prep[i]=-1;
        pree[i]=0;
        flow[i]=inf; 
                //      
    }
    cost[s]=0;
    que.push(s);
    vis[s]=true;
    prep[s]=0;pree[s]=0;flow[s]=inf;
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        vis[now]=false;
        for (int i=head[now];i;i=e[i].next)
        {
            if (e[i].val>0&&cost[e[i].to]>cost[now]+e[i].pri)
            {
                cost[e[i].to]=cost[now]+e[i].pri;   
                flow[e[i].to]=min(flow[now],e[i].val);
                prep[e[i].to]=now;
                pree[e[i].to]=i;
                if (!vis[e[i].to]) 
                {
                    vis[e[i].to]=true;
                    que.push(e[i].to);
                }
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
void EK(int s,int t)
{
    int delta=SPFA(s,t);
    while (delta!=-1)
    {
        ans+=delta;tot+=delta*cost[t];
        for (int j=t;j;j=prep[j])
        {
            e[pree[j]].val-=delta;
            e[pree[j]^1].val+=delta;
        }
        delta=SPFA(s,t);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    cnt=1;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w,&f);
        add(u,v,w,f);
        add(v,u,0,-f);//          
    }
    EK(s,t);
    printf("%d %d",ans,tot);
    return 0;
}