图论算法-最小费用最大流模板【EK;Dinic】

---

EK模板

const int inf=1000000000;
int n,m,s,t;
struct node{int v,w,c;};
vector<node> map[10010];
int flow[10010][10010];
bool inq[10010];
int d[10010];
int pre[10010],pref[10010];
int minc,maxf;

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w,c;
        cin>>u>>v>>w>>c;
        map[u].push_back((node) {v,w,c});
        map[v].push_back( (node) {u,0,-c});
    }

    queue<int> q;
    while(1)
    {
        fill(d,d+1+n,inf);
        d[s]=0;
        q.push(s);
        inq[s]=true;

        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            inq[u]=false;

            for(int j=0;j<map[u].size();j++)
            {
                int v=map[u][j].v;
                int w=map[u][j].w;
                int c=map[u][j].c;

                if(w>flow[u][v]&&d[u]+c<d[v])
                {
                    d[v]=d[u]+c;
                    pre[v]=u;
                    pref[v]=w;
                    if(!inq[v])
                    {
                        inq[v]=true;
                        q.push(v);
                    }
                }
            }
        }

        if(d[t]==inf)
        break;

        int a=inf;
        for(int u=t;u!=s;u=pre[u])
        a=min(a,pref[u]-flow[ pre[u] ][u]);

        for(int u=t;u!=s;u=pre[u])
        {
            flow[ pre[u] ][u]+=a;
            flow[ u ][ pre[u] ]-=a;
        }
        minc+=d[t]*a;
        maxf+=a;
    }

    cout<<maxf<<" "<<minc;
    return 0;
}

---

Dinic模板

其实就是把最大流Dinic中的层次图改成了求最短路

记得反向边的费用要取反

const int inf=2139062143;
int n,m;
int s,t;
int fee,ans,tot=1;//ans是最大流;fee是最小费用
struct node{int v,f,c,nxt;}E[1000010];
int head[1000010];
int lev[1000010];
int d[1000010];
bool inq[1000010];

int read()
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

void add(int u,int v,int cap,int cost)
{
    E[++tot].nxt=head[u];
    E[tot].v=v;
    E[tot].f=cap;
    E[tot].c=cost;
    head[u]=tot;
}

bool bfs()
{
    memset(d,127,sizeof(d));
    d[s]=0;
    queue<int> q; q.push(s);
    inq[s]=true;

    while(!q.empty())
    {
        int u=q.front();
        q.pop(); inq[u]=false;
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].v;
            if(E[i].f&&d[u]+E[i].c<d[v])
            {
                d[v]=d[u]+E[i].c;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    if(d[t]!=inf)return true;
    else return false;
}

int dfs(int u,int cap)
{
    if(u==t)
    return cap;

    int flow=cap;
    inq[u]=true;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(d[v]==d[u]+E[i].c&&E[i].f>0&&flow&&!inq[v])
        {
            int f=dfs(v,min(flow,E[i].f));
            E[i].f-=f;
            E[i^1].f+=f;
            fee+=E[i].c*f;
            flow-=f;
        }
    }
    inq[u]=false;
    return cap-flow;
}

int main()
{
    n=read();m=read();
    s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),f=read(),c=read();
        add(u,v,f,c);add(v,u,0,-c);
    }

    while(bfs())
    ans+=dfs(s,inf);

    cout<<ans<<" "<<fee;
    return 0;
}