假期ACM提升计划start!!!
问题情景
如图,网络中有两台计算机$s$和$t$和其他若干计算机,计算机之间用光缆连接,每条光缆都有一个最大传输速率。现在想从$s$传输数据到$t$,问$s$到$t$最大传输率是多少。
网络流基础知识
网络流基础概念
网络流的研究对象为有向图。
流相关
有源点$s$和汇点$t$,$s$能无限的提供流量,$s$出发的流量最终回汇聚到$t$,且所有的边的边权都为正的有向图称为容量网络。上图的计算机网络就是一个容量网络。有向图中的边称为弧,边权称为弧的容量。弧上实际的流量被称为弧的流量。所有这些弧的流量所组成的集合叫做网络流。
每条弧上的流量不超过其容量,且除了源点和汇点之外,每个点的流出的流量和流入的流量相等的网络流叫做可行流。由物理知识可知,研究可行流比较有意义。在一个可行流中,源点流出的流量总和称为可行流的流量。所谓的最大流就是最大的可行流的流量。
对于顶点序列$(s, U_1, U_2,…, U_n, t)$,这样一个顶点序列,如果相邻顶点间均有一条边,(无论正向还是逆向),这个序列就被称为一条链,和链方向一致的弧称为前向弧,相反的弧称为后向弧。如图
对于一条可行流中的一条链来说,满足
- 所有前向弧的流量小于其容量
- 所有后向弧的流量大于0
就称它为一条增广路。(增广路就是通过这条路径能使可行流流量增加的路径)
显然对于一条增广路来说,增加其上正向弧的流量或减小反向弧的流量,就会让可行流的流量增大。
割相关
$割$是一个边的集合,如果将这个集合中的边删去,图就分为两个联通分量$S$和$T$。如果$sS$,$TT$,就称这是一个$S-T$割。
割的容量为从$S$向$T$所有的连边的容量之和。就是任意$S$中的顶点到$T$中顶点的前向弧的容量之和。容量最小的割就是最小割。 割的流量为任意$S$中的顶点到$T$中顶点的所有的前向弧的流量之和减去所有的后向弧的流量之和。
最大流最小割定理
定理内容
最大流的流量=最小割的容量
证明
命题一:对于可行流的任意一个割,割的流量=可行流的流量。
证明:
可行流中,对于任何一个非s和t的顶点,有流入这个顶点的流量=流出这个顶点的流量。对于S-T割中S集合中的所有非s的顶点,则有所有的前向弧的流量之和减去所有的后向弧的流量之和为0,再考虑原点s,则所有的前向弧的流之和减去所有的后向弧的流量之和=s流出的流量总和,也就是可行流的流量。而根据割的流量定义,也恰好就是一个割的流量。
命题二:可行流的流量一定小于等于任何一个割的容量。
由命题一可知,可行流的流量=割的流量$\leqslant$割的容量。
命题三:对于可行流$G$,设其流量为$f$,如下三个命题等价:
- 存在一个割使得割的容量$c=f$。
- $f$是最大流。
- $G$中不存在任何增广路。
证明:
$1 \Rightarrow 2$
由命题一可知,可行流的流量的最大可能值就为割的容量的最小值,如果存在一个割使$c=f$,则$f$一定是最大流量,也就是最大流。
$2 \Rightarrow 3$
证明其逆否命题,$G$中存在增广路,则$f$不是最大流。
若$G$中存在真广路,由增广路的定义可知,$f$的流量一定可以增大,则$f$不是最大流。
$3 \Rightarrow 1$
$G$中不存在增广路,意味着从$s$到$t$的所有链中一定存在饱和前向弧(流量=容量)或者零流后向弧(流量=0),说明可行流$G$中,源点不通过饱和前向弧或者零后向弧无法达汇点。我们可以构造这样一个点集$S$,为可行流G中经过非饱和前向弧和非零后向弧就可以到达的顶点。其余顶点放入点集$T$中。则$S$和$T$之间的弧一定没有非饱和前向弧或者非零后向弧,即所有$S$和$T$之间的弧,一定要都是饱和前向弧或者零后向弧,则$S$和$T$所对应的$S-T$割有:\(割的流量=前向弧的流量-后向弧的流量=前向弧的容量-0=前向弧容量=割的容量\)
则由命题一可知,可行流的流量=割的流量$\leqslant$割的容量=割的流量。即存在一个割使得割的容量$c = f$。
由上面的讨论我们就可以证明最大流=最小割。同时我们也有了一种找到最大流的方法,就是不断调整可行流的流量使可行流中不存在增广路。这时可行流的流量就是最大流。
PS:以下算法中的增广路定义和上面的并不相同。以下为残差网络中的增广路。。
算法
Ford-Fulkerson算法
算法介绍
(wiki百科)只要有一条从源点(开始节点)到汇点(结束节点)的路径,在路径的所有边上都有可用容量,就沿着这条路径发送一个流,流量由路径上的最小容量限制。 然后再找到另一条路径,一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。
步骤:
- dfs搜索出一条增广路。
- 增广路上每条弧都用这条弧的流量反向建边。
- 重复执行1,直到没有增广路为止。
这些非零反向边和原图中的非饱和边组成的有向图称为残余网络。每次增广就是在残余网络上增广,当不存在增广路时,就获得了最大流。
模板
// 洛谷P3376 T了两个点,玄学复杂度。。。
#include <bits/stdc++.h>
#define fast_io \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
const int onf = 0xcfcfcfcf;
const int N = (int)1e5 + 5;
const int M = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
const double esp = 1e-8;
//------------天佑AC------------------
struct Edge {
int v;
ll w;
int rev;
};
void add(vector<vector<Edge>> &g, vector<vector<int>> &flag, int u, int v, int w) {
if (flag[u][v] == -1) {
g[u].push_back((Edge){v, w, g[v].size()});
g[v].push_back((Edge){u, 0, g[u].size() - 1});
flag[u][v] = g[u].size() - 1;
flag[v][u] = g[v].size() - 1;
} else {
g[u][flag[u][v]].w += w;
}
}
ll dfs(vector<vector<Edge>> &g, vector<bool> &vis, int u, int t, ll f) {
if (u == t)
return f;
vis[u] = true;
for (int i = 0; i < g[u].size(); ++i) {
Edge &e = g[u][i];
if (!vis[e.v] && e.w > 0) {
ll d = dfs(g, vis, e.v, t, min(f, e.w));
if (d > 0) {
e.w -= d;
g[e.v][e.rev].w += d;
return d;
}
}
}
return 0;
}
ll Ford_Fulkerson(vector<vector<Edge>> &g, int s, int t) {
ll flow = 0, f = 0;
do {
vector<bool> vis(g.size());
f = dfs(g, vis, s, t, llinf);
flow += f;
} while (f != 0);
return flow;
}
int main() {
fast_io;
int n, m, s, t;
cin >> n >> m >> s >> t;
vector<vector<Edge>> g(n + 1);
vector<vector<int>> flag(n + 1, vector<int>(n + 1, -1));
for (int u, v, w, i = 0; i < m; ++i) {
cin >> u >> v >> w;
add(g, flag, u, v, w);
}
cout << Ford_Fulkerson(g, s, t) << endl;
return 0;
}int head[N]; // n为点个数
int cnt = 0;
struct Edge {
int v, w;
int nxt;
} edge[M]; // m为边个数
void init() {
memset(head, -1, sizeof(head));
cnt = 0;
}
void add(int u, int v, int w) {
edge[cnt].w = w;
edge[cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
复杂度分析
时间复杂度:$O(F \lvert E \rvert)$
每次流量可能增加1,最多进行F次深搜,复杂度和$F$有关,效率较低,容易被卡。
关于为什么加了个vis数组,不会遗漏增广路的问题。
如下图,可能会有人有这样的想法,如果我们从1->2->4->5找不到增广路,但是1->3->4->5可能找到增广路,就会因为我在遍历第一条路径时标记了顶点vis[4] = true,使第二条路径无法走通。
不会,因为如果1->2->4->5上没有一条增广路的话,有两种情况,一种是–>2或者2->4这条路径上有饱和弧,这种情况下,就不会从2遍历到4,另一种情况下是4->5这条路径上有饱和弧,那么1->3->4->5这条路径就不是增广路。
综上,不会因为vis标记而遗漏增广路。
Dinic算法
算法介绍
是一位大神在算法课前想出来的
Dinic算法也是利用增广路的思想。最主要利用了最短增广路在增广之后,不会出现更短的增广路这个性质,同时Dinic也利用了一种叫做分层图的思想。
分层图就是通过顶点距离源点的远近(这个远近指的是两点之间边的数量)进行分层。用$bfs$来给点标记距离,记录在数组$depth$中,同一距离的点就处在同一层。我们使用$dfs$在这个分层图上寻找增广路,限制在增广过程中,只有满足$depth[u] + 1 == depth[v]$的弧$<u, v>$才能用来增广(形成增广路)。这样我们在$dfs$中找到的总是最短的增广路。这个最短的增广路可能有多条。我们需要进行多次$dfs$。如果找不到一条增广路,说明最短增广路一定变长。(我们就获得了当前图的阻塞流)我们就再一次使用$bfs $进行分层再用$dfs$增广。直到$bfs$后发现汇点不能到达为止。
关于最短增广路在增广之后,不会出现更短的增广路这个性质的简要说明。
我们每次增广增加的边都为反向边。假设出现原图不存在的更短的路径$p’$,$p’$一定会经过这些原先不存在的反向边,也就是说一定会经过反向边$<v,u>$到达原先最短路径$p$上的某个顶点$u$。这个顶点可以把这最短路径分成前后两部分($p_1,p_2,p’_1,p’_2$)。我们可以知道这个顶点以后的路径$p’_2$不可能比$p_2$更短,那么只有可能是$p_1 < p’_1$。这显然是不合理的,因为我们到达$v$的路径不可能比原来更短,再经过$<u,v>$到达$u$的路径一定会比原来更长。
综上,不会出现更短的路径且也不会出现与原来等长的路径。如果还有和原来等长的路径,一定是原来图中就存在的,而不是增广以后通过反向边新出现的。
结合最短增广路在增广之后不会变短这个性质,在增广之后,一个点的距离源点的距离不会变短,即这个点的距离标记不会变小。而在图阻塞之后,进行$bfs$获得的新分层图,能在下一个分层图用来增广的点(除了源点)
(是不是只有上一轮用过的点会变大,待考虑),层次一定会变大。因为这些点有可能通过反向边进行增广,路径一定会变长。(我觉得这也是$ISAP$的基础)
模板
#include <bits/stdc++.h>
#define fast_io \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
const int onf = 0xcfcfcfcf;
const int N = (int)1e5 + 5;
const int M = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
const double esp = 1e-8;
//------------天佑AC------------------
struct Edge {
int v;
ll w;
int rev;
};
void add(vector<vector<Edge>> &g, vector<vector<int>> &flag, int u, int v, int w) {
if (flag[u][v] == -1) {
g[u].push_back((Edge){v, w, g[v].size()});
g[v].push_back((Edge){u, 0, g[u].size() - 1});
flag[u][v] = g[u].size() - 1;
flag[v][u] = g[v].size() - 1;
} else {
g[u][flag[u][v]].w += w;
}
}
bool bfs(const vector<vector<Edge>> &g, vector<int> &depth, int s, int t) {
queue<int> que;
vector<int>(g.size(), 0).swap(depth);
depth[s] = 1;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = 0; i < g[u].size(); ++i) {
const Edge &e = g[u][i];
if (!depth[e.v] && e.w > 0) {
depth[e.v] = depth[u] + 1;
que.push(e.v);
}
}
}
if (depth[t] != 0)
return true;
return false;
}
ll dfs(vector<vector<Edge>> &g, vector<int> &depth, vector<int> &cur, int u, int t, ll flow) {
if (u == t)
return flow;
for (int &i = cur[u]; i < g[u].size(); ++i) {
Edge &e = g[u][i];
if (depth[e.v] == depth[u] + 1 && e.w > 0) {
ll d = dfs(g, depth, cur, e.v, t, min(flow, e.w));
if (d > 0) {
e.w -= d;
g[e.v][e.rev].w += d;
return d;
}
}
}
return 0;
}
ll Dinic(vector<vector<Edge>> &g, int s, int t) {
ll flow = 0;
vector<int> depth;
while (bfs(g, depth, s, t)) {
vector<int> cur(g.size(), 0);
while (ll d = dfs(g, depth, cur, s, t, llinf)) {
flow += d;
}
}
return flow;
}
int main() {
fast_io;
int n, m, s, t;
cin >> n >> m >> s >> t;
vector<vector<Edge>> g(n + 1);
vector<vector<int>> flag(n + 1, vector<int>(n + 1, -1));
for (int u, v, w, i = 0; i < m; ++i) {
cin >> u >> v >> w;
add(g, flag, u, v, w);
}
cout << Dinic(g, s, t) << endl;
return 0;
}
优化
当前弧优化
我们可以知道对于一个分层图。我们如果已经$dfs$到了一个顶点的某一条边,一定是这个顶点这条边之前边已经不能被增广(已经被搾干)。我们可以用一个数组记录当前顶点$dfs$到了哪个顶点,这样就能节省下大量时间,且保证了每条边只被遍历了一次。(非常管用)
炸点优化
如果通过一个点增广,收益为0,那么这个点在这个分层图中,肯定没用了。直接depth[u] = -1
,将这个点排除。(感觉没啥用)
dfs多路优化
我们可以通过一次$dfs$将一个分层图中所有的增广路都找出来,而不是多次dfs从而节省了时间。(可能因为常数原因,我在验证板子的时候更慢了….)
具体做法如下。
ll dfs(vector<vector<Edge>> &g, vector<int> &depth, vector<int> &cur, int u, int t, ll flow) { //只调用一次
ll nowflow = 0;
if (u == t)
return flow;
for (int &i = cur[u]; i < g[u].size() && nowflow != flow; ++i) {
Edge &e = g[u][i];
if (depth[e.v] == depth[u] + 1 && e.w > 0) {
if (ll d = dfs(g, depth, cur, e.v, t, min(flow - nowflow, e.w))) {
e.w -= d;
g[e.v][e.rev].w += d;
nowflow += d;
}
}
}
if (!nowflow)
depth[u] = -1;
return nowflow;
}
伸缩操作
待学。能将复杂度优化为$O(nmlog(F))$。
复杂度分析
复杂度:$O(E * V^2)$
为什么要分层。This is a question!!! 我们可以发现如果每次$bfs$后,路径长度都会$+1$,且$v$个顶点,路径长度最多就是$v-1$。也就是我们最多使用$v-1$次分层,形成$v-1$个分层图。这个复杂度是$O(V)$的。同时每次我们经过当前弧优化,能保证每条边最多只被遍历$V - 1$次。$dfs$的复杂度是$O(E*V)$ 的,故复杂度上界为$O(E * V^2)$,但一般会比这个好的多。
为啥$dfs$复杂度中会有那个$V$,考虑一个点,最多有$V - 1$个点可以通向这个点。对应边最多被访问$O(V)$。
ISAP算法
算法介绍
Improved Shortest Augumenting Path
采用增广路的最大流算法的复杂度上界是$O(E*V^2)$,无法改善,但是我们可以通过改良实现过程来减少运行时间。ISAP可以认为是一种改良的Dinic算法。
Dinic算法是不断$bfs$划分层次图和$dfs$增广这两个过程来获得最大流。而ISAP算法的思想就是仅进行一次$bfs$初始化,之后在$dfs$过程中维护层次图。
我们具体操作为先逆向$bfs$一次得到层次图(从$t$开始$bfs$),然后在不断进行与Dinic相同的$dfs$增广,这部分我们进行多路优化,即一次增广,找到所有当前最短长度的增广路 。之后让所有在当前分层图不能进行增广的层数都变为他所有所有连接的点的度数最小的那个$+1$。以让增广继续下去。直到,depth[s] = head.size();
,也就是达到增广路可能的最大值 。
以下内容为引用:permui
如果一开始把距离标号都设为0,那么$dfs$最多需要$O(n^2)$来把距离标号初始化,而我们可以最开始逆向$bfs$一次,$O(n+m)$初始化所有距离标号。
GAP优化:如果距离标号出现了断层,那么显然不存在新的增广路。我们用一个gap数组记录每种层次标号有多少个,如果当前修改了最后一个某种层次标号,那么就出现了前后断层,结束算法。
当前弧优化:增广过程中,如果一个点的标号没有修改过,那么它已经遍历过的边不需要再遍历一次,所以我们存下每次遍历到哪条边,下一次从这条边开始遍历(因为有可能到这里之后流量用完了,但是还没有增广完)。
最短路的修改具有连续性,即我们不需要每次求后继的标号最小值,而是直接给标号加一。(个人觉得就是距离标号一定是递增的)
同Dinic中,如果流量用完了直接退出。
关于为什么要反向$bfs$初始化,我觉得最重要的原因是为了GAP优化。
为什么当出现了断层就不会有新的增广路? 因为我们在更新标号时显然会先更新较小的标号(dfs序)。这样更新过程中如果出现了某个标号消失,后面的大标号只会变得更大,也就是没有点能将这个断层填补上,也就不存在增广路了。如果是正序则无法达到这个效果。
#include <bits/stdc++.h>
#define fast_io \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
const int onf = 0xcfcfcfcf;
const int N = (int)1e5 + 5;
const int M = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
const double esp = 1e-8;
//------------天佑AC------------------
struct Edge {
int v;
ll w;
int next;
};
struct ISAP {
vector<Edge> edge; // 链式前向星
vector<int> head;
vector<int> gap; // 统计每个深度点的数量,GAP优化,
vector<int> depth; // 保留深度信息
vector<int> cur; // 当前边优化
vector<vector<int>> flag; // 用来去掉重边,可以去掉。
void add(int u, int v, int w) {
if (flag[u][v] == -1) {
edge.push_back((Edge){v, w, head[u]});
flag[u][v] = head[u] = edge.size() - 1;
edge.push_back((Edge){u, 0, head[v]});
flag[v][u] = head[v] = edge.size() - 1;
} else {
edge[flag[u][v]].w += w;
}
}
bool bfs(int s, int t) {
++gap[depth[t] = 1];
queue<int> que;
que.push(t);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].v;
if (!depth[v]) {
++gap[depth[v] = depth[u] + 1];
que.push(v);
}
}
}
if (depth[s] == 0)
return false;
return true;
}
ll dfs(int u, int s, int t, ll flow) {
if (u == t)
return flow;
ll nowflow = 0;
for (int &i = cur[u]; i != -1; i = edge[i].next) {
Edge &e = edge[i];
if (e.w && depth[u] == depth[e.v] + 1) {
ll tmp = dfs(e.v, s, t, min(flow - nowflow, e.w));
if (tmp)
nowflow += tmp, e.w -= tmp, edge[i ^ 1].w += tmp;
if (nowflow == flow)
return nowflow;
}
}
if (!(--gap[depth[u]])) //GAP优化
depth[s] = head.size();
if (depth[u] != head.size())
++gap[++depth[u]], cur[u] = head[u];
return nowflow;
}
ll maxflow(int s, int t) {
ll ret = 0;
if (bfs(s, t)) {
cur = head;
while (depth[s] < head.size()) {
ret += dfs(s, s, t, llinf);
}
}
return ret;
}
ISAP(int n, int m) {
head.assign(n + 1, -1);
gap.assign(n + 1, 0);
depth.assign(n + 1, 0);
flag.assign(n + 1, vector<int>(n + 1, -1));
edge.reserve(m << 1);
}
};
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
ISAP solve(n, m);
for (int u, v, w, i = 0; i < m; ++i) {
cin >> u >> v >> w;
solve.add(u, v, w);
}
cout << solve.maxflow(s, t) << endl;
return 0;
}
复杂度分析
复杂度:$O(E * V^2)$
与Dinic相同,但是应该更高效一些。
写在最后
预退流法,和算法中不明白的小细节还很多,未完待续把。。。
感谢permui的ISAP博客。
部分内容来自《挑战程序设计竞赛》。
其他的博文也参考了很多,无法一一列举,有的也无法查处源头,见谅。