[BZOJ1834/LuoguP2604][ZJOI2010]network 网络扩容

题目链接：

BZOJ1834

LuoguP2604

首先，第一问就是裸的最大流，直接\(Dinic\)往上套就行了。

至于第二问，把跑完最大流剩下的图费用看为\(0\)，对原图的每一条边复制一条新边，容量为\(k\)(\(\infty\)也行)，费用为\(w\)。

然后直接跑一遍\(MCMF\)即可。

流量限制？新建一个源点\(St\)，从\(St\)向\(1\)连一条容量为\(k\)，费用为\(0\)的边，以新点跑费用流即可。

时间复杂度：\(O(n^2m+nmk)\)（毕竟上界）

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

int n,m,Moe,St,Ed;
int us[5005],vs[5005],cs[5005],ws[5005];
int Head[1005],Next[40005],To[40005],Val[40005],Cos[40005],En=1;
int Dep[5005],Ref[5005],Pre[5005];

inline void Add(int x,int y,int z,int w)
{
    Next[++En]=Head[x],To[Head[x]=En]=y,Val[En]=z,Cos[En]=+w;
    Next[++En]=Head[y],To[Head[y]=En]=x,Val[En]=0,Cos[En]=-w;
}

bool BFS()
{
    std::queue<int> q;
    memset(Dep,0,sizeof Dep);
    q.push(St),Dep[St]=1;
    while(!q.empty())
    {
        int x=q.front(),y;
        q.pop();
        for(int i=Head[x];i;i=Next[i])
            if(Val[i]&&!Dep[y=To[i]])
            {
                Dep[y]=Dep[x]+1;
                if(y==Ed)return true;
                q.push(y);
            }
    }
    return false;
}

int Dinic(int x,int Flow)
{
    if(x==Ed)return Flow;
    int k,Rest=Flow,y;
    for(int i=Head[x];i;i=Next[i])
        if(Val[i]&&Dep[y=To[i]]==Dep[x]+1)
        {
            k=Dinic(y,std::min(Rest,Val[i]));
            if(!k){Dep[y]=0;continue;}
            Val[i]-=k,Val[i^1]+=k,Rest-=k;
        }
    return Flow-Rest;
}

int SPFA()
{
    std::queue<int> q;
    memset(Dep,0x3f,sizeof Dep);
    q.push(St),Dep[St]=0,Ref[St]=1<<30;
    while(!q.empty())
    {
        int x=q.front(),y;
        q.pop();
        for(int i=Head[x];i;i=Next[i])
            if(Val[i]&&Dep[y=To[i]]>Dep[x]+Cos[i])
            {
                Dep[y]=Dep[x]+Cos[Pre[y]=i];
                Ref[y]=std::min(Ref[x],Val[i]);
                q.push(y);
            }
    }
    if(Dep[Ed]==0x3f3f3f3f)return 0;
    for(int x=Ed,i;x!=St;x=To[i^1])
        Val[i=Pre[x]]-=Ref[Ed],Val[i^1]+=Ref[Ed];
    return Dep[Ed]*Ref[Ed];
}

int main()
{
    scanf("%d%d%d",&n,&m,&Moe),St=1,Ed=n;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&us[i],&vs[i],&cs[i],&ws[i]);//边的备份
        Add(us[i],vs[i],cs[i],0);
    }
    int MaxFlow=0,Fs;
    while(BFS())
        while((Fs=Dinic(St,0x3f3f3f3f)))
            MaxFlow+=Fs;//求解问题1 Dinic
    for(int i=1;i<=m;++i)Add(us[i],vs[i],Moe,ws[i]);
    St=n+1,Add(St,1,Moe,0);//流量限制
    int MinCost=0,Cs;
    while((Cs=SPFA()))MinCost+=Cs;//求解问题2 EK
    printf("%d %d\n",MaxFlow,MinCost);
    return 0;
}

[BZOJ1834/LuoguP2604][ZJOI2010]network 网络扩容

原文：https://www.cnblogs.com/LanrTabe/p/10149845.html