跳至内容
旧博客（算法竞赛）
最大流&&费用流 板子整理

最大流&&费用流 板子整理

旧博客（算法竞赛） 发表于 原文更新于 2020-03-28

3 种费用流在 loj 上测试的结果：

  1. EK + dij 5584ms
  2. Dinic + spfa 4649ms
  3. Dinic + dij 4870ms

推荐使用 dinic + dij，出题人人均卡 spfa …

网络流

注意以下模板默认编号范围为 1~n，请确保所有编号（包括源汇点）都在此范围内，以防初始化不全。

最大流

Dinic 用容量不为 0 的边构建层次图，在层次图上有方向的进行多路增广。

int n,m,S,T;
struct edge
{
    int u,v,next;
    LL flow;
}e[N*2];
int pre[MAXN],cur[MAXN],cnt=1;
void add(int u,int v,LL flow)
{
    e[++cnt]={u,v,pre[u],flow},pre[u]=cnt;
}
int dis[MAXN],q[MAXN];
bool bfs() //构建分层图
{
    int h=1,t=0;
    mst(dis,0),q[++t]=S,dis[S]=1;
    while(h<=t)
    {
        int u=q[h++];
        for(int i=pre[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(!dis[v]&&e[i].flow)
                dis[v]=dis[u]+1,q[++t]=v;
        }
    }
    return dis[T];
}
LL dfs(int u,LL flow) //多路增广
{
    if(u==T||!flow)return flow;
    LL ret=0,d=0;
    for(int i=cur[u];i;i=e[i].next)
    {
        int v=e[i].v; cur[u]=i; //当前弧优化
        if(dis[v]==dis[u]+1&&e[i].flow)
        {
            d=dfs(v,min(flow-ret,e[i].flow));
            if(d)ret+=d,e[i].flow-=d,e[i^1].flow+=d;
            if(ret==flow)return ret;
        }
    }
    return ret;
}
LL dinic()
{
    LL ans=0;
    while(bfs())
    {
        fp(i,1,n)cur[i]=pre[i];
        ans+=dfs(S,linf);
    }
    return ans;
}
int work()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    fp(i,1,m)
    {
        int u,v;LL flow;
        scanf("%d%d%lld",&u,&v,&flow);
        add(u,v,flow),add(v,u,0);
    }
    return printf("%lld\n",dinic());
}

费用流

1. Dinic Bfs改最短路算法

将 Dinic 中的 bfs 构建层次图改成最短路算法（Spfa或带势函数的Dijkstra），每次沿着最短路图的方向进行增广。

Spfa 
int n,m,S,T;
struct edge{int u,v,next;LL flow,w;}e[N];
int pre[MAXN],cur[MAXN],cnt=1;
void add(int u,int v,LL flow,LL w){e[++cnt]={u,v,pre[u],flow,w},pre[u]=cnt;}

bool vis[MAXN];
int q[MAXN],h,t; LL dis[MAXN];
bool spfa()//建议用stl queue 手写要换成循环队列防越界
{
    fp(i,1,n)dis[i]=linf; mst(vis,0);
    h=1,t=0,vis[S]=1,dis[S]=0,q[++t]=S;
    while(h<=t)
    {
        int u=q[(h++)%MAXN]; vis[u]=0; 
        gow(u)if(e[i].flow&&dis[v]>dis[u]+w)
        {
            dis[v]=dis[u]+w;
            if(!vis[v])vis[v]=1,q[(++t)%MAXN]=v;
        }
    }
    return dis[T]<linf;
}
lpr ans;
LL dfs(int u,LL flow)
{
    if(u==T||!flow) return ans.fi+=flow,ans.se+=dis[u]*flow,flow;
    LL ret=0,d; vis[u]=1; //vis标记 防止在费用为 0 的边上反复跳
    for(int i=cur[u];i;i=e[i].next)
    {
        int v=e[i].v;LL w=e[i].w; cur[u]=i;
        if(e[i].flow&&dis[u]+w==dis[v]&&!vis[v])
        {
            d=dfs(v,min(e[i].flow,flow-ret));
            if(d) e[i].flow-=d,e[i^1].flow+=d,ret+=d;
            if(ret==flow)return ret;
        }
    }
    return ret;
}
void mcf()
{
    while(spfa())
    {
        mst(vis,0);
        fp(i,1,n)cur[i]=pre[i];   
        dfs(S,linf);
    }
}
int work()
{
    scanf("%d%d",&n,&m); scanf("%d%d",&S,&T);
    fp(i,1,m)
    {
        int u,v; LL f,w;
        scanf("%d%d%lld%lld",&u,&v,&f,&w);
        add(u,v,f,w),add(v,u,0,-w);
    }
    mcf();
    return printf("%lld %lld\n",ans.fi,ans.se);
}
Dijkstra 
int n,m,S,T;
struct edge{int u,v,next;LL flow,w;}e[N];
int pre[MAXN],cur[MAXN],cnt=1;
void add(int u,int v,LL flow,LL w)
{
    e[++cnt]={u,v,pre[u],flow,w},pre[u]=cnt;
}
bool vis[MAXN];
LL dis[MAXN],h[MAXN];
bool dij()
{
    priority_queue<lpr> q;
    fp(i,1,n)dis[i]=linf;
    dis[S]=0,q.push({0,S});
    while(!q.empty())
    {
        int u=q.top().se; LL d=-q.top().fi; q.pop();
        if(d!=dis[u])continue;
        gow(u)if(e[i].flow&&dis[u]+w+h[u]-h[v]<dis[v])
            dis[v]=dis[u]+w+h[u]-h[v],q.push({-dis[v],v});
    }
    //fp(i,1,n)cout<<dbgs2(i,dis[i])<<endl;
    return dis[T]<linf;
}
lpr ans;
LL dfs(int u,LL flow)
{
    //cout << dbgs(u) << endl;
    if(u==T||!flow) return ans.fi+=flow,ans.se+=(dis[u]+h[u])*flow,flow;
    LL ret=0,d; vis[u]=1;
    for(int i=cur[u];i;i=e[i].next)
    {
        int v=e[i].v;LL w=e[i].w; cur[u]=i;
        if(e[i].flow&&dis[u]+w+h[u]-h[v]==dis[v]&&!vis[v])
        {
            d=dfs(v,min(e[i].flow,flow-ret));
            if(d) e[i].flow-=d,e[i^1].flow+=d,ret+=d;
            if(ret==flow)return ret;
        }
    }
    return ret;
}
void mcf()
{
    while(dij())
    {
        mst(vis,0);
        fp(i,1,n)cur[i]=pre[i];   
        dfs(S,linf);
        fp(i,1,n)if(dis[T]<linf)h[i]+=dis[i]; //维护势函数
    }
}
int work()
{
    scanf("%d%d",&n,&m); 
    scanf("%d%d",&S,&T);
    fp(i,1,m)
    {
        int u,v; LL f,w;
        scanf("%d%d%lld%lld",&u,&v,&f,&w);
        add(u,v,f,w),add(v,u,0,-w);
    }
    mcf();
    return printf("%lld %lld\n",ans.fi,ans.se);
}

2.EK

Dijkstra 
int n,m,S,T;
struct edge{int u,v,next;LL flow,w;}e[N];
int pre[MAXN],cur[MAXN],cnt=1;
void add(int u,int v,LL flow,LL w)
{
    e[++cnt]={u,v,pre[u],flow,w},pre[u]=cnt;
}
bool vis[MAXN];
LL dis[MAXN],h[MAXN];
int from[MAXN];
bool dij()
{
    priority_queue<lpr> q;
    fp(i,1,n)dis[i]=linf;
    dis[S]=0,q.push({0,S});
    while(!q.empty())
    {
        int u=q.top().se; LL d=-q.top().fi; q.pop();
        if(d!=dis[u])continue;
        gow(u)if(e[i].flow&&dis[u]+w+h[u]-h[v]<dis[v])
            dis[v]=dis[u]+w+h[u]-h[v],q.push({-dis[v],v}),from[v]=i;
    }
    return dis[T]<linf;
}
lpr ans;
void mcf()
{
    while(dij())
    {
        LL flow=linf;
        for(int u=T;u!=S;u=e[from[u]].u)
            flow=min(flow,e[from[u]].flow);
        ans.fi+=flow,ans.se+=(dis[T]+h[T])*flow;
        for(int u=T;u!=S;u=e[from[u]].u)
            e[from[u]].flow-=flow,
            e[from[u]^1].flow+=flow;
        fp(i,1,n)if(dis[i]<linf)h[i]+=dis[i];
    }
}
int work()
{
    scanf("%d%d",&n,&m); 
    scanf("%d%d",&S,&T);
    fp(i,1,m)
    {
        int u,v; LL f,w;
        scanf("%d%d%lld%lld",&u,&v,&f,&w);
        add(u,v,f,w),add(v,u,0,-w);
    }
    mcf();
    return printf("%lld %lld\n",ans.fi,ans.se);
}
网络流24题 简要题解线段树分治小结