本文考虑的是自最费用最大流问题。
最大流问题的标号法：
1.对初始点找有裕量的下一跳，用深度优先一路走下去，一直到终点为止，那么取这条路最小的一段的裕量。当然裕量也包括反向可以减少的量。
2.将这个裕量更新到这条路经的每个点上。
3.重复1，一直到找不到再有通往终点的裕量为止。那么此时就是最大流量。
最大流量最小费用问题：
将其分为两个不同的问题：
1.最小费用（加权距离）
2.最大流量（用标号算法）。
一般的思路是可以用D斯特拉算法对最小费用进行求解。再求出最消费用的路线后求解最大流。
1.清空流量，找出最短路径。
2.对该路径求最大流量。
3.更新流量，继续寻找最短路径。
4.找最大流
当然本博客由特给了最简单高效的方法：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;const int maxn = 1e5+10;
struct node {int to,w,f,nxt;
} e[maxn];
int n,m,s,t,maxflow,mincost;
int dis[maxn],flow[maxn],via[maxn],pre[maxn],last[maxn];
int head[maxn],cnt=0;void addedge( int u, int v, int f, int w )
{e[cnt].to = v;e[cnt].f = f;e[cnt].w = w;e[cnt].nxt = head[u];head[u] = cnt++;
}int spfa()
{memset(dis,inf,sizeof(dis));memset(flow,inf,sizeof(flow));memset(via,0,sizeof(via));queue <int> Q;Q.push(s); via[s]=1; dis[s]=0; pre[t]=-1;while ( !Q.empty() ) {int x = Q.front(); Q.pop(); via[x]=0;for ( int i=head[x]; i!=-1; i=e[i].nxt ) {int y = e[i].to, f=e[i].f, w=e[i].w;if ( f && dis[y]>dis[x]+w ) { // 只要最短流能更新就更新dis[y] = dis[x] + w;pre[y] = x; // y 的父节点是xlast[y] = i; // y点连接其父节点的边，编号为iflow[y] = min(flow[x],f); // 源点到y点的最大流量。会被最小的一个分支限制住if ( via[y]==0 ) { // 只有队列中没有当前值才往队列里加。Q.push(y); via[y]=1;}}}}return pre[t]!=-1; // 判断汇点是否有点连入，即还存不存在增广路。初始化pre[t]=-1.
}void MCMF()
{maxflow = mincost = 0;while ( spfa() ) { // 还存在增广路就进入int x = t;maxflow += flow[t]; // 源点到t点的最大流量mincost += flow[t]*dis[t];while ( x!=s ) { // 递归改变边的流量e[last[x]].f -= flow[t];e[last[x]^1].f += flow[t];x = pre[x];}}
}int main()
{int x,y,f,w;memset(head,-1,sizeof(head));cin >> n >> m >> s >> t;for ( int i=0; i<m; i++ ) {cin>>x>>y>>f>>w;addedge( x,y,f,w ); //建立正向边addedge( y,x,0,-w ); // 反向边，流量为0, 权值为-w}MCMF();cout << maxflow << " " << mincost << endl;return 0;
}
————————————————
版权声明：本文为CSDN博主「才子词人自是白衣卿相」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43828245/article/details/102822111