网络流
1.关于网络的一些定义：
(1)网络：
网络（又称流网络 \(Flow \ Network\)）是指一个有向图\(\ G=(V,E)\)。
每条边\((u,v)\in E\)都有个权值\(c(u,v)\),称之为容量\((Capacity)\),\(\forall (u,v)\notin E,c(u,v)=0\).
其中有两个特殊点:分别是源点\((Source)s\in V\)和汇点\((Sink) \ t\in V (s \neq t)\)(可以简单理解为起点和终点)
(2)流
设\(f(u,v)\)是定义在二元组\((u\in V,v\in V)\) 上的实数函数且满足一下3点
1). 容量限制:对于每条边，流经该边的流量不得超过该边的容量,即\(f(u,v)<=c(u,v)\)(这个其实很好理解，比如你家下水道水流量只有一定阈值，超过这个阈值你就不能再多流了)
2).斜对称性:每条边流量与其相反边流量之和为零即\(f(u,v)+f(v,u)=0\)
3).流守恒性：从源点流出的流量等于汇点流入的流量，即\(\forall x\in V -\{s,t\} ,\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E }f(x,v)\)
那么\(f\)成为网络\(G\)的流函数.对于\((u,v)\in E,f(u,v)\)称为边的流量,\(c(u,v)-f(u,v)\)称为边的剩余容量，整个网络流量为\(\sum_{(s,v)\in E}f(s,v)\),即从源点发出的所有流量之和.
一般而言也可以把网络流理解为整个图的流量，流量均满足上述性质.
2.网络流的常见问题
1).最大流
我们有一张图，要求从源点向汇点的最大流量（可以有很多条路到达汇点）,就是最大流问题.
2).最小费用最大流
最小费用最大流问题：每条边都有一个费用，代表单位流量经过这条边的开销.我们要在求出最大流的同时,要求花费费用最小.
3).最小割
割其实就是删边的意思，当然最小割是删掉\(X\)条边来让\(S\)跟\(T\)不相通.我们要求\(X\)条边加起来流量总和最小.这为最小割问题.
----------------------------------------------（分割线）
以下是算法部分
2.最大流
本页面主要介绍最大流问题相关的算法知识
(1)\(Ford-Fulkerson\)增广
\(Ford-Fulkerson\)增广式计算最大流的一类算法总称.该算法运用贪心思想，通过寻找增广路来更新并求解.
概述
网络\(G\)和\(G\)上的流\(f\)定义见上.
我们将\(G\)中所有节点和剩余容量大于0的边构成的子图称为残量网络\(G_f(Residual \ Network)\),即\(G_f=(V,E_f)\),其中\(E_f={(u,v)|c_f(u,v)>0}\).(这里要注意的是下文将会介绍到流量可能为负值，因此，\(E_f\)的边不一定在\(E\)中.)
我们将\(G_f\)上一条从源点\(s\)到回电\(t\)的路径称为增广路\((Augmenting Path)\).对于一条增广路,我们给每一条边\((u,v)\)都加上等量的流量,以令整个网络流量增加.这一过程称为增广\((Augment)\).由此，最大流的求解可以被视为若干次增光分别得到流的叠加.值得注意的是,根据流的斜对称性，我们在增广式应该退流,即\(f(u,v)\)增加时\(f(v,u)\)要减少同等量.我们方便讨论,在{\((u,v)\)是正向的}的前提下，我们称(v,u)为反向边.
Tips:在最大流算法的代码实现中，我们往往需要支持快速访问反向边的操作。在邻接矩阵中，这一操作是 trivial(琐碎的)的(\(g_{u,v}\)<->\(g_{v,u}\))主流做法是用链式前向星.一个常用技巧:令边从偶数(通常是0)开始编号,并在加边时总是紧接着加入其反向边使他们编号相邻.由此,我们可以令编号为\(i\)的边和编号为\(i \ xor \ 1\)的边始终保持互为反向边的关系.
初次接触可能会遇到违反直觉的情形--反向边的流量可能是个负值.实际上我们可以注意到,在增广过程中真正有意义的是剩余容量\(c_f\),而\(f(v,u)\)的绝对值是不重要的,我们可以将它的减少视为\(c_{f}(v,u)\)的增加.
假设\(G\)是一个单位容量的网络,考虑一下过程:
\(\quad\) 1).\(G\)上有多条增广路,其中,我们选择进行一次先后经过\(u,v\)的增广,流量增加1.
\(\quad\) 2).我们注意到,如果进行中图上的增广,这个局部最大流量不是1是2.但由于指向\(u\)的边和从\(v\)出发的边在第一次增广中耗尽了容量,此时我们无法进行中图上的增广.这意味着我们当前的流量是不够优的,但局部可能已经没有其它的增广路了.
\(\quad\) 3).现在引入退流操作，第一次增广后，退流意味着\(c_f{v,u}\)增加了1剩余容量，即相当于新增\((v,u)\)这条边,因此我们可以再进行一次先后经过\(p,v,u,q\)的增广。无向边\((u,v)\)上的流量在两次增广中抵消,我们惊奇的发现这一结果实际上和中图等价的.
由上可知,退流带来的\(抵消\)效果使我们无需担心我们按照\(错误\)顺序选择增广路.
容易发现,只要\(G_f\)上存在增广路,那么对其增广就可以令总流量增加;否则说明总流量一定达到最大可能值.在整数流量的网络\(G=(V,E)\)上,\(Ford-Fulkerson\)增广时间复杂度上界:\(O(|E||f|)\),其中\(f\)是\(G\)
上最大流.这是因为单轮增广时间复杂度为\(O(|E|)\),而增广会导致总流量增加,故增广轮数不可能超过\(|f|\).
\(Ford-Fulkerson\)增广的实现:
(1).\(Edmonds-Karp\)算法
思想
· 如果在\(G_f\)上我们可以从\(s\)出发BFS到\(t\),则我们找到了新的增广路.
· 对于增广路\(p\),我们计算出\(p\)经过的边的剩余容量的最小值\(\Delta = min_{(u,v)\in p}c_f(u,v)\).\(\quad\)我们给\(p\)上的每条边都加上\(\Delta\),令最大流增加\(\Delta\).
· 因为我们修改流量,所以我们得到形\(G_f\),我们在新的\(G_f\)上重复上述过程,直至增广路不存在,流量不增加.
时间复杂度:\(O(|V||E|^2)\)(一眼顶针,鉴定为废物算法,写费用流可以用)
code:
#define maxn 250
#define INF 0x3f3f3f3f
struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct EK {
int n, m; // n：点数，m：边数
vector<Edge> edges; // edges：所有边的集合
vector<int> G[maxn]; // G：点 x -> x 的所有边在 edges 中的下标
int a[maxn], p[maxn]; // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
// p：点 x -> BFS 过程中最近接近点 x 的边
void init(int n) {
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int Maxflow(int s, int t) {
int flow = 0;
for (;;) {
memset(a, 0, sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int i = 0; i < G[x].size(); i++) { // 遍历以 x 作为起点的边
Edge& e = edges[G[x][i]];
if (!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i]; // G[x][i] 是最近接近点 e.to 的边
a[e.to] =
min(a[x], e.cap - e.flow); // 最近接近点 e.to 的边赋给它的流
Q.push(e.to);
}
}
if (a[t]) break; // 如果汇点接受到了流，就退出 BFS
}
if (!a[t])
break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
for (int u = t; u != s;
u = edges[p[u]].from) { // 通过 u 追寻 BFS 过程中 s -> t 的路径
edges[p[u]].flow += a[t]; // 增加路径上边的 flow 值
edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值
}
flow += a[t];
}
return flow;
}
};
(2).\(Dinic\)算法
思想
考虑在增广前先对\(G_f\)做BFS分层,即根据节点\(u\)的源点\(s\)的距离\(dist(u)\)把节点分成若干层.令经过\(u\)的流量只能流向下一层的节点\(v\),即删除\(u\)想层数标号相等或者更小的节点的出边,我们成\(G_f\)剩下的部分为层次图\((Level Graph)\).形式化地,我们称\(G_L=(V,E_L)\)是\(G_f=(V,E_f)\)的层次图,其中\(E_L=\{ (u,v) | (u,v)\in E_f ,dist(u)+1=d(v)\}\).
如果我们在层次图\(G_L\)上找到一个增广流\(f_b\),使得仅在\(G_L\)上是不可能找出更大的增广流的,则我们称\(f_b\)是\(G_L\)的阻塞流\((Block Flow)\).
注意:尽管上文中我们仅在单挑增广路上定义了增广/增广流,广义地, 增广 一词不仅可以用于单条路径上的增广流,也可以用于若干增广流的并--后者才是我们定义阻塞流时使用的意义.
定义层次图和阻塞流后,\(Dinic\)算法的流程如下.
1).在\(G_f\)上\(BFS\)出层次图\(G_L\).
2).在\(G_L\)上DFS出阻塞流\(f_b\).
3).将\(f_b\)并到原先的流\(f\)中,\(f \gets f +f_b\)
4).重复以上过程直到不存在从\(s\)到\(t\)的路径.
此时\(f\)即为最大流.
弧优化:
注意到\(G_L\)上DFS的过程中,如果结点\(u\)同事具有大量入边和出边,并且\(u\)每次接受来自入边的流量时都便利出边表来决定将流量传递给哪条出边,则\(u\)这个局部的时间复杂度最坏可达\(O(|E|^2)\).为避免这一缺陷,如果某一时刻我们已经直到边\((u,v)\)已经增广到极限(边\((u,v)\)已经没有剩余容量或者\(v\)的后侧已增广至阻塞),则\(u\)的流量没有必要再尝试流向出边\((u,v)\).根据这个缘故,对于每个结点\(u\),我们维护\(u\)的出边表中第一条还有必要尝试的出边.习惯上,我们称维护这个指针为当前弧,我们成这个做法叫做当前弧优化.
多路增广
多路增广是\(Dinic\)算法的一个常数优化--如果我们在层次图上找到一条从\(s\)到\(t\)的增广路\(p\),
则接下来我们未必需要重新从\(s\)出发找下一条增广路,而可能从\(p\)上最后一个仍有剩余容量的位置出发寻找一条岔路进行增广.考虑到其回溯形式的一致性,这一优化在\(DFS\)的代码实现中也是自然的.(多路增广不影响复杂度的常数优化).
实现:
#include <bits/stdc++.h>
using namespace std;
const long long inf=2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[520010];
int tot=1,now[520010],head[520010];
struct node {
int to,net;
long long val;
} e[520010];
inline void add(int u,int v,long long w) {
e[++tot].to=v;//如果使用e[++tot]这样形式来加边,请将tot初值赋为1
e[tot].val=w;
e[tot].net=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].net=head[v];
head[v]=tot;
}
inline int bfs() { //在残量网络中构造分层图
for(register int i=1;i<=n;i++) dis[i]=inf;
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty()) {
int x=q.front();
q.pop();
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(e[i].val>0&&dis[v]==inf) {
q.push(v);
now[v]=head[v];
dis[v]=dis[x]+1;
if(v==t) return 1;
}
}
}
return 0;
}
inline int dfs(int x,long long sum) { //sum是整条增广路对最大流的贡献
if(x==t) return sum;
long long k,res=0; //k是当前最小的剩余容量
for(register int i=now[x];i&∑i=e[i].net) {
now[x]=i; //当前弧优化
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf; //剪枝，去掉增广完毕的点
e[i].val-=k;
e[i^1].val+=k;
res+=k; //res表示经过该点的所有流量和（相当于流出的总量）
sum-=k; //sum表示经过该点的剩余流量
}
}
return res;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&t);
for(register int i=1;i<=m;i++) {
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
while(bfs()) {
ans+=dfs(s,inf); //流量守恒（流入=流出）
}
printf("%lld",ans);
return 0;
}
//code by @Eleven谦
\(MPM\)算法
大家都不学那我就不写了(’∇’)シ┳━┳
\(ISAP\)
Step:
1).和\(Dinic\)算法一样,我们还是先跑BFS对图上的点进行分层,不过与\(Dinic\)略有不同,我们在反图上,从\(t\)到\(s\)进行BFS.
2).执行完1).后,我们通过DFS找最短路.
3).增广过程和\(Dinic\)过程类似,我们只选择比当前点层数少1的点来增广(因为我们分层是从t->s,所以从s->t应该每次层数少1)
然后与\(Dinic\)不同,我们不会重新来跑一次BFS来对图上的点重新分层,而是在增广过程中就完成重分层过程.
具体说,设\(i\)号点的层数为\(dep_i\),当我们结束再\(i\)号点的增广过程后,我们在遍历残量网络上\(i\)的所有出边,找到层最小的出点\(j\),随后令\(d_i=d_j+1\).特别地,若残量网络上\(i\)无出边.则\(d_i\)=n.
容易发现,当\(d_s>=n\)时,图上不存在增广路,此时可以终止算法.
与\(Dinic\)类似,\(ISAP\)也存在 当前弧优化
而\(ISAP\)还存在另一个优化,我们记录层数为\(i\)的点的数量\(num_i\),每当将一个点的层数从\(x\)更新到\(y\)的时候,更新\(num\)数组的值,若在更新后\(num_x=0\),意味着图上出现断层,无法找到增广路,此时直接终止算法(实现时直接将\(d_s\)标记为\(n\)),此优化称为\(GAP优化\)
\(Push-Relabel\)预流推进算法
该方法在求解过程中忽略流守恒性,并对每个节点更新信息,以求解最大流
通用的预流退进算法
首先我们介绍预流推进算法的主要思想,以及一个可行的暴力实现算法.
预流推进算法通过对单个节点的更新操作,直到没有节点需要更新来求解最大流.
算法过程维护的流函数不一定保持流守恒形,对于一个节点,我们允许进入节点的流超过流出节点的流,
超过的部分被称为节点\(u(u\in V-\{s,t\})\)的 超额流 \(e(u)\):
\(e(u)=\sum\limits_{(x,u)\in E}{f(x,u)}-\sum\limits_{(u,y)\in E}{f(u,y)}\)
若\(e(u)>0\)称节点u\(溢出\),注意当我们提到溢出节点时,不包括\(s和t\).
预留推进算法维护每个结点的高度\(h(u)\),冰洁规定溢出的节点\(u\)如果要推送超额流,
只能向高度小于\(u\)的结点推送;如果\(u\)没有相邻的高度小于\(u\)的结点,就修改\(u\)的高度(重贴标签)
高度函数
准确地说,预留推进维护以下的一个映射\(h:V->N:\)
· \(h(s)=|V|,h(t)=0\)
· \(\forall (u,v)\in E_f, h(u)<=h(v)+1\)
称\(h\)是残量网络\(G_f=(V_f,E_f)\)的高度函数
引理1:设\(G_f\)上的高度函数为\(h\),对于任意两个节点\(u,v\in V\)如果\(h(u)>h(v)+1\),则\((u,v)\)不是\(G_f\)中的边.
算法只会在\(h(u)=h(v)+1\)的边执行推送
推送(Push)
适用条件:结点\(u\)溢出,且存在节点\(v((u,v)\in E_f,c(u,v)-f(u,v)>0,h(v)=h(v)+1)\),则\(push\)操作使用于\((u,v)\).
于是,我们尽可能将超额流从\(u\)推送到\(v\),推送过程中我们只关心超额流\(c(u,v)-f(u,v))\)的最小值,不关心\(v\)是否溢出.
如果\((u,v)\)在推送玩之后满流,将其从残量网络中删除.
重贴标签(Relabel)
适用条件:如果节点\(u\)溢出,且\(\forall (u,v)\in E_f,h(u)<=h(v)\),则relabel操作使用于\(u\).
则将\(h(u)\)更新为\(min_{(u,v)\in E_f}h(v)+1\)即可.
初始化
\(\forall (u,v)\in E,f(u,v)= \begin{cases} c(u,v) ,u=s\\ 0 ,otherwise\end{cases}\)
\(u\in V,h(u)=\begin{cases}|V|,u=s \\ 0,otherwise \end{cases}\)
$e(u) = \sum\limits_{(x,u)\in E} f(x,u)- \sum\limits_{(u,y)\in E}f(u,y) $
上述将\((s,v)\in E\)充满流,并将\(h(s)\)抬高,使得\((s,v)\notin E_f\),因为\(h(s)>h(v)\)而且\((s,v)\)毕竟满流,没必要留在残量网络中;上述还将\(e(s)\)初始化为\(\sum\limits_{(s,v)\in E}f(s,v)\)为相反数.
\(HLPP\)算法
最高标号预流推进算法(\(Highest Label Preflow Push\))在上述通用的预流推进算法是,都优先选择高度最高的溢出节点,其算法复杂度为\(O(n^2\sqrt m)\)
\(HLPP\)算法过程如下:
1.初始化(基于预留推进算法);
2.选择溢出结点中高度最高的结点\(u\),并对它所有可以推送的边进行推送;
3.如果\(u\)仍然溢出,对他重新贴上标签,回到步骤2;
4.如果没有溢出的节点,算法结束.
BFS优化
\(HLPP\)的上界为\(O(n^2 \sqrt m)\),但是在使用时卡的比较紧;我们可以再初始化高度时进行优化.具体地,我们初始化\(h(u)\)为dis(u,t);特别地,\(h(s)=n\)
在\(BFS\)的同时我们顺便检查图的联通性,[排除误解情况.
GAP优化
\(HLPP\)推送的条件是\(h(u)=h(v)+1\),而如果在算法的某一时刻,\(h(u)=t\)的节点个数为0,那么对于\(h(u)>t\)的节点就永远无法推送的到超额流到\(t\),因此只能送回\(s\),那么我们就在这时直接让他们的高度变成至少\(n+1\),以尽快推送回\(s\),减少重贴标签的操作.
我们可以使用\(N*2-1\)个痛\(B\),其中\(B[i]\)中记录所有当前高度为\(i\)的溢出节点.加入了以上提到的两种优化.并且只处理了高度小于\(n\)的溢出结点.
(持续更新中其实就是从oiwiki爬下来当笔记的,一个一个手敲非粘贴,代码是在学习过程中在题解中搞下来的代码)
3.最小割
概念
割
对于一个网络流图\(G=(V,E)\),其割的定义为一种带你的划分方式:将所有的点划分为S和T=V-S两个集合,其中源点\(s\in T\),回电\(t\in T\)
割的容量
我们定义割\((S,T)\)的容量\(c(S,T)\)表示所有从\(S\)到\(T\)的边的容量之和,即\(c(S,T)=\sum\limts_{u\in S,v\in T}c(u,v)\).
最小割
最小割就是求得一个割\((S,T)\)使得割的容量\(c(S,T)\)最小.
最大流最小割定理
定理 :\(f(s,t)_{max}=c(s,t)_{min}\)
code(其实就是最大流的\(Dinic\)算法...):
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
const int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N];
void add(int u, int v, int w) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); }
int bfs(int s, int t) {
memset(dep, 0, sizeof(dep));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dep[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (val[i] && !dep[v]) q.push(v), dep[v] = dep[u] + 1;
}
}
return dep[t];
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (val[i] && dep[v] == dep[u] + 1) {
int x = dfs(v, t, std::min(val[i], flow - ans));
if (x) val[i] -= x, val[i ^ 1] += x, ans += x;
}
}
if (ans < flow) dep[u] = -1;
return ans;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
int x;
while ((x = dfs(s, t, 1 << 30))) ans += x;
}
return ans;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
}
printf("%d\n", dinic(s, t));
return 0;
}
ps:由于最大流=最小割,所以我们可以直接用\(Dinic\)来求最小割
求出所有\(S\)点集内的点,我们可以通过源点\(s\)开始\(DFS\)每次都走残量大于0的边.
割边数量
如果需要再最小割的前提喜爱最小化割边数量,那么先求出最小割,把没有满流的边改成\(\infty\).满流的边容量改成 1,重新跑一遍最小割就可以去出最小割边数量;如果没有最小割的前提,直接把所有边容量设成1,求一遍最小割即可.
问题模型1
有n个物品和两个集合\(A,B\),如果一个物品没有放入\(A\)会花费\(a_i\),没有放入\(B\)会花费\(b_i\);还有若干个形如\(u_i,v_i,w_i\)的限制条件,如果\(u_i\)和\(v_i\)同时不在一个集合会花费\(w_i\).每个物品必须且只能属于一个集合,求最小代价.
这时一个景点 二者选其一 的最小割题目.我们对于每个集合设置源点\(s\)和汇点\(t\),第\(i\)个点由\(s\)连一条容量为\(a_i\)的边,向\(t\)连一条容量为\(b_i\)的边.对于限制条件\(u,v,w\),我们在\(u,v\)之间连容量为\(w\)的双向边.
注意到当源点和汇点不相连的时候,代表这些点都选择其中一个集合.如果将连向\(s\)或\(t\)的边割开,表示不放在\(A\)或\(B\)集合,如果吧物品之间的边割开,表示这两个物品不放在同一集合.
最小割即最小花费.
问题模型
最大权值闭合图,即给定一张有向图,每个点都有一个权值(可以为正或负或0),你需要选择一个权值和最大子图,使得子图中每个点的后继都在子图中.
做法:建立超级源点\(s\)和超级汇点\(t\),若节点\(u\)权值为正,则\(s\)向\(u\)连一条有向边,边权即为该点点权;
若节点权值为负,则由\(u\)向\(t\)连一条有向边,边权即为该点点权的相反数.原图上所有边权改为\(\infty\).跑网络最大流,将所有正权值之和减去最大流,即为答案.
费用流
给定一个网络\(G=(V,E)\),每条边除了有容量限制\(c(u,v)\),还有一个单位流量的费用\(w(u,v)\).
当\(u,v\)的流量为\(f(u,v)\)时,需要花费\(f(u,v)·w(u,v)\)的费用.
\(w\)也满足斜对称性,即\(w(u,v)=-w(v,u)\).
则该网络中总花费最小的最大流称为最小费用最大流,即在最大化\(\sum\limits_{(s,v)\in E}f(s,v)\)的前提下最小化\(\sum\limits_{(u,v)\in E}f(u,v)·w(u,v)\).
SSP算法
\(SSP(Successive Shortest Path)\)算法是一个贪心算法.他的思路是每次寻找单位费用最早的增广路进行增广,直到图上不存在增广路为止.
如果图上存在单位费用为负的圈,SSP算法无法正确求出该网络的最小费用最大流.
此时,需要先用消圈算法消去图上的负圈.
实现(基于\(Dinic\)算法):
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
bool vis[N];
void add(int u, int v, int w, int c) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dis[s] = 0, vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (cap[i] && dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i];
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != INF;
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
vis[u] = 1;
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
int x = dfs(v, t, std::min(cap[i], flow - ans));
if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
}
}
vis[u] = 0;
return ans;
}
int mcmf(int s, int t) {
int ans = 0;
while (spfa(s, t)) {
int x;
while ((x = dfs(s, t, INF))) ans += x;
}
return ans;
}
int main() {
int s, t;
scanf("%d%d%d%d", &n, &m, &s, &t);
while (m--) {
int u, v, w, c;
scanf("%d%d%d%d", &u, &v, &w, &c);
addedge(u, v, w, c);
}
int ans = mcmf(s, t);
printf("%d %d\n", ans, ret);
return 0;
}