【题目来源】
【题目描述】
给定一个包含 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)。---
【算法代码：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 10out:
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 10out:
20 300
*/
【参考文献】