2023年7月30日发(作者：)

⽹络流之费⽤流求费⽤流⽬前好像只有EK+SPFA改版，时间复杂度为O(N*E*k)，其中K为最⼤流值。但时间上的期望时间复杂度为：O(A*E*K)，其中A为所有顶点进队列的平均次数，可以证明A⼀般⼩于等于2。最⼩费⽤最⼤流：#include using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 205;struct node{ int v, to, w, cost, next;}edge[maxn*maxn];int no, n, m, s, t;int head[maxn], dis[maxn], vis[maxn], pre[maxn], rec[maxn];queue q;inline void init(){ no = 0; memset(head, -1, sizeof head);}inline void add(int u, int v, int w, int f){ edge[no].v = v; edge[no].w = w; edge[no].cost = f; edge[no].next = head[u]; head[u] = no++; edge[no].v = u; edge[no].w = 0; edge[no].cost = -f; edge[no].next = head[v]; head[v] = no++;}int SPFA(int s, int t){ memset(dis, 0x3f, sizeof dis); memset(vis, 0, sizeof vis); while(!()) (); (s); dis[s] = 0; vis[s] = 1; while(!()) { int tp = (); (); vis[tp] = 0; int k = head[tp]; while(k != -1) { if(dis[edge[k].v] > dis[tp] + edge[k].cost && edge[k].w) { dis[edge[k].v] = dis[tp] + edge[k].cost; pre[edge[k].v] = tp; rec[edge[k].v] = k; if(vis[edge[k].v] == 0) { vis[edge[k].v] = 1; (edge[k].v); } } k = edge[k].next; } } if(dis[t] == inf) return 0; return 1;}pair Mcmf(int s, int t){ int minflow, k, mincost = 0, maxflow = 0; int minflow, k, mincost = 0, maxflow = 0; while(SPFA(s, t)) { k = t; minflow = inf; while(k != s) { minflow = min(minflow, edge[rec[k]].w); k = pre[k]; } k = t; maxflow += minflow; while(k != s) { mincost += minflow*edge[rec[k]].cost; edge[rec[k]].w -= minflow; edge[rec[k]^1].w += minflow; k = pre[k]; } } return make_pair(maxflow, mincost);}int main(){ int u, v, w, f; scanf("%d %d %d %d", &n, &m, &s, &t); init(); for(int i = 1; i <= m; ++i) { scanf("%d %d %d %d", &u, &v, &w, &f); add(u, v, w, f); } pair ans = Mcmf(s, t); cout << << " " << << endl; return 0;}有时候也会遇到最⼤费⽤最⼤流，其实只要在建图时将所有费⽤取负，最后求的最⼩费⽤取负就是最⼤费⽤。最⼩费⽤最⼤流是指满⾜源点流出的流量最⼤时，总费⽤最⼩的⼀个⽹络，模板都是基于此。最⼤费⽤最⼤流则是将所有的费⽤取负，然后再跑⼀遍最⼩费⽤最⼤流，将最终的最⼩费⽤取负就是最⼤流量下的最⼤费⽤了。最⼤费⽤可⾏流关注的是费⽤⽽⾮流量是否最⼤，那么当我们在寻找可改进路时如果从源点到汇点的dis变成⼤于0的时侯，则表明可改进路不会再减少费⽤了，所以在SPFA寻找增⼴路时return的条件改为dis[t] <= 0即可。最⼩费⽤可⾏流没有意义。继续加油~