AcWing 2174：[模板] 费用流 ← Dinic / EK + SPFA

【题目来源】
https://www.acwing.com/problem/content/2176/

【题目描述】
给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量和费用，边的容量非负。
图中可能存在重边和自环，保证费用不会存在负环。
求从 S 到 T 的最大流，以及在流量最大时的最小费用。

【输入格式】
第一行包含四个整数 n,m,S,T。
接下来 m 行，每行三个整数 u,v,c,w，表示从点 u 到点 v 存在一条有向边，容量为 c，费用为 w。
点的编号从 1 到 n。

【输出格式】
输出点 S 到点 T 的最大流和流量最大时的最小费用。
如果从点 S 无法到达点 T 则输出 0 0。

【输入样例】
5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10​​​​​​​

【输出样例】
20 300

【数据范围】
2≤n≤5000,
1≤m≤50000,
0≤c≤100,
−100≤w≤100
S≠T​​​​​​​

【算法分析】
● 百度百科：SPFA 算法是 Bellman-Ford 算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。--- https://blog.csdn.net/hnjzsyjyj/article/details/138425339

【算法代码：Dinic算法 + SPFA】

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=5e3+5,M=1e5+5;
const int INF=0x3f3f3f3f;

int h[N],e[M],ne[M],cap[M],val[M],idx;
int fv[N],fe[N]; //fv:前驱点, fe:前驱边
int dis[N]; //源点到各点最小费用
bool st[N]; //SPFA入队标记
int d[N]; //Dinic层次
int cur[N]; //Dinic当前弧优化
int n,m,S,T;

void add(int a,int b,int c,int w) {
    cap[idx]=c,val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    cap[idx]=0,val[idx]=-w,e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}

bool spfa() {
    memset(dis,INF,sizeof dis);
    memset(st,false,sizeof st);
    memset(d,0,sizeof d);
    dis[S]=0,d[S]=1;
    queue<int> q;
    q.push(S);
    st[S]=true;

    while(!q.empty()) {
        int u=q.front();
        q.pop();
        st[u]=false;
        for(int i=h[u]; ~i; i=ne[i]) {
            int v=e[i];
            if(cap[i]>0 && dis[v]>dis[u]+val[i]) {
                dis[v]=dis[u]+val[i];
                d[v]=d[u]+1;
                fv[v]=u, fe[v]=i;
                if(!st[v]) {
                    q.push(v);
                    st[v]=true;
                }
            }
        }
    }
    return dis[T]!=INF;
}

int dfs(int u,int lim) {
    if(u==T) return lim;
    int flow=0;
    for(int i=cur[u]; ~i && flow<lim; i=ne[i]) {
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1 && cap[i] && dis[v]==dis[u]+val[i]) {
            int t=dfs(v,min(cap[i],lim-flow));
            if(!t) d[v]=-1;
            cap[i]-=t,cap[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

pair<LL,LL> min_val_max_flow() {
    LL flow=0,res=0;
    while(spfa()) {
        memcpy(cur,h,sizeof cur);
        int t;
        while((t=dfs(S,INF))>0) {
            flow+=t;
            res+=t*dis[T];
        }
    }
    return make_pair(flow,res);
}

/*pair<LL,LL> min_val_max_flow() {
    LL flow=0,res=0;
    while(spfa()) {
        int minc=INF;
        for(int v=T; v!=S; v=fv[v]) {
            minc=min(minc,cap[fe[v]]);
        }
        flow+=minc;
        res+=minc*dis[T];

        for(int v=T; v!=S; v=fv[v]) {
            int i=fe[v];
            cap[i]-=minc;
            cap[i^1]+=minc;
        }
    }
    return make_pair(flow,res);
}*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h,-1,sizeof h);

    cin>>n>>m>>S>>T;
    for(int i=0; i<m; i++) {
        int a,b,c,w;
        cin>>a>>b>>c>>w;
        add(a,b,c,w);
    }

    pair<LL,LL> ans=min_val_max_flow();
    cout<<ans.first<<" "<<ans.second<<endl;

    return 0;
}

/*
in:
5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10

out:
20 300
*/

【算法代码：EK算法 + SPFA】

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=5e3+5, M=1e5+5;
const int INF=0x3f3f3f3f;
int h[N],e[M],ne[M],cap[M],val[M],idx;
int fv[N],fe[N]; //fv:前驱点, fe:前驱边
int dis[N];
bool st[N];
int n,m,S,T;

void add(int a,int b,int c,int w) {
    cap[idx]=c,val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    cap[idx]=0,val[idx]=-w,e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}

bool spfa() {
    memset(dis,INF,sizeof dis);
    memset(st,false,sizeof st);
    dis[S]=0;
    queue<int> q;
    q.push(S);
    st[S]=true;

    while(!q.empty()) {
        int u=q.front();
        q.pop();
        st[u]=false;
        for(int i=h[u]; ~i; i=ne[i]) {
            int v=e[i];
            if(cap[i]>0 && dis[v]>dis[u]+val[i]) {
                dis[v]=dis[u]+val[i];
                fv[v]=u, fe[v]=i;
                if(!st[v]) {
                    q.push(v);
                    st[v]=true;
                }
            }
        }
    }
    return dis[T]!=INF;
}

pair<LL,LL> min_val_max_flow() {
    LL flow=0,res=0;
    while(spfa()) {
        int minc=INF;
        for(int v=T; v!=S; v=fv[v]) {
            minc=min(minc,cap[fe[v]]);
        }
        flow+=minc;
        res+=minc*dis[T];

        for(int v=T; v!=S; v=fv[v]) {
            int i=fe[v];
            cap[i]-=minc;
            cap[i^1]+=minc;
        }
    }
    return make_pair(flow,res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h,-1,sizeof(h));

    cin>>n>>m>>S>>T;
    for(int i=0; i<m; i++) {
        int a,b,c,w;
        cin>>a>>b>>c>>w;
        add(a,b,c,w);
    }

    pair<LL,LL> ans=min_val_max_flow();
    cout<<ans.first<<" "<<ans.second<<endl;

    return 0;
}

/*
in:
5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10

out:
20 300
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/161317988
https://blog.csdn.net/hnjzsyjyj/article/details/161545392
https://blog.csdn.net/hnjzsyjyj/article/details/138425339

 

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/hnjzsyjyj/article/details/161546484