「学习笔记」网络流
点击查看目录
目录
定义部分名词括号内写个英文是为了方便起函数名变量名。
\rvalue/\rvalue/\rvalue/\rvalue/\rvalue/
仅提供大致思路,想看详细点的看上面链接。
建议学的时候自己多手画几个图模拟一下。
常见建模套路,打算以后单开一个博写,因为还有好多套路没有学。
知识点
一些基础定义
主要来自 OI-wiki。
-
「网络(Flow Network)」:指一张有向图 \(G = (V, E)\)。
-
「容量(Capacity)」:在一个网络中,对于每一组边 \((u, v) \in E\) 都有一个权值 \(c(u, v)\) 被称为容量。若 \((u, v) \not\in E\) 则 \(c(u, v) = 0\)。
-
「源点(Source)与汇点(Sink)」:两种存在于网络中的比较特殊的点,所有流从源点 \(s(s\in V)\) 流出,最后流入汇点 \(t(t\in V)\),\(s\neq t\)。
-
「流(Flow)」:若函数 \(f(u, v)\) 满足以下三点性质:
- 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 \(f(u,v)\leq c(u,v)\)。
- 斜对称性:每条边的流量与其相反边的流量之和为 0,即 \(f(u,v)=-f(v,u)\)。
- 流守恒性:从源点流出的流量等于汇点流入的流量,即 \(\sum_{(s, u)\in E}f(s,u)=\sum_{(u, t)\in E}f(u,t)\)。
则 \(f\) 是网络 \(G\) 的流函数。
对于每一条边 \((u, v)\in E\),\(f(u, v)\) 被称为边 \((u, v)\) 的「流量」,\(c(u, v) - f(u, v)\) 被称为边 \((u, v)\) 的「剩余流量」。
所有流从源点 \(s(s\in V)\) 流出,因此整个网络流量为 \(\sum_{(s, u)\in E}f(s,u)\)。
最大流
- 「最大流(Max-flow)」:给定一个网络,求一个流函数使这个网络的总流量最大。
Ford-Fulkerson 算法(增广路算法)
- 「增广路(Augmenting Path)」:一条起点为源点,终点为汇点的剩余流量不为空的边的路径。
这里的增广路与二分图中的不是一个,但是是一个思想。
考虑不断从源点出发寻找增广路并将其跑满,但是这样是错的,因为你增广出来的不一定是最优解里需要的,考虑使这个操作「可撤销」。
解决办法是建立反向边,原来的边流量减多少反向边加多少(流的斜对称性),可以把原来的边上不优的流通过反向边推到另一条边上。
下图是从 OI-wiki 拿的,可以感性理解一下:
但是这玩意复杂度保证不了啊!有可能会出现下图这种情况(from rvalue):
graph LR; s-->|23333333|1 1-->|23333333|t 1-->|1|2 2-->|23333333|t s-->|23333333|2可能会出现流在容量为 \(1\) 的那条边被反复推的情况,这个时候复杂度就取决于值域了。
Edmonds-Karp 算法
简称 EK 算法。
考虑每次找增广路时找最短的增广路。这个直接 01 最短路找,时间复杂度 \(O(E)\)。
不难发现这样找到的增广路长度单调不减,最长为 \(V\),那么考虑迭代次数即可算出时间复杂度。
每次跑增广路都会有一条边流量被跑满,我们称这样的边为「关键边」。每次跑增广路都会出现一条关建边,那么所有边成为「关键边」次数之和即为迭代次数。一条边成为关键边之后暂时会从图中消失,再次出现必须跑其反向边,这时增广路长度必然增加,那么每条边最多 \(V\) 会成为「关键边」,总迭代次数是 \(VE\) 次。
因此总时间复杂度是 \(O(VE^2)\)。
感觉还是不够快,观察发现原因是每次最短的增广路有很多条,但是每次只增广一条。
继续优化。
Dinic 算法
思考如何一次性把所有最短增广路跑了。
按与源点的距离建立分层图,然后跑一遍 DFS 把全图的最短路跑满。
乍一看感觉层数严格递增,DFS 遍历所有点,复杂度是 \(O(VE)\) 的,但是 DFS 中一个点会重复经过所以不能保证其复杂度。
考虑两个优化:
- 无用点优化
如果有流量流向一个点的时候这个点流不动了,说明它在当前分层图上不再能做出贡献,可以暂时删去。 - 当前弧优化
决定复杂度,不会负优化,你慢了说明你挂了。
如果当前到点 \(u\) 的流在 \(u\) 遍历完其指向的所有点时用完了,我们记录一下是推向哪条边时用完的,下次再搜索到 \(u\) 时直接从这条边开始推,因为之前的肯定推满了。
考虑计算时间复杂度。
参考 EK 算法时间复杂度的证明,每次找增广路最多找 \(E\) 条,长度最多为 \(V\),分层图层数严格递增,最多会建 \(V\) 次分层图,时间复杂度上限为 \(O(V^2E)\)。
注意到计算复杂度时用词都是「最多」,稍微想一想就会发现不可能跑满,这个复杂度上限是非常松的,一般出题人不会卡你,卡了也没关系,因为这样干就不会有什么人能过题了。
下面是一份实现:
namespace GRAPH {
class Edge { public: ll v, w, r; };
class Graph {
private:
ll n, s, t, c[N][N];
std::vector <Edge> tu[N];
public:
inline void Init (ll _n, ll _s, ll _t) {
n = _n, s = _s, t = _t;
return;
}
inline void AddEdge (ll u, ll v, ll w) {
c[u][v] += w;
ll p1 = tu[u].size (), p2 = tu[v].size ();
tu[u].push_back ((Edge){v, w, p2});
tu[v].push_back ((Edge){u, 0, p1});
return;
}
private:
ll dep[N], cur[N];
public:
ll maxflow;
private:
inline bool DinicBFS () {
memset (dep, 0, sizeof (dep));
std::queue <ll> q;
q.push (s), dep[s] = 1, cur[s] = 0;
while (!q.empty ()) {
ll u = q.front (); q.pop ();
far (p, tu[u]) {
if (!p.w || dep[p.v]) continue;
dep[p.v] = dep[u] + 1, cur[p.v] = 0;
if (p.v == t) return true;
q.push (p.v);
}
}
return false;
}
inline ll DinicDFS (ll u, ll flow) {
if (u == t || flow <= 0) return flow;
ll sum = 0, sz = tu[u].size () - 1;
for (ll &i = cur[u]; i <= sz; ++i) {
Edge &p = tu[u][i];
if (!p.w || dep[p.v] != dep[u] + 1) continue;
ll k = DinicDFS (p.v, std::min (flow, p.w));
if (k <= 0) dep[p.v] = 0;
p.w -= k, tu[p.v][p.r].w += k;
sum += k, flow -= k;
if (flow <= 0) break;
}
return sum;
}
public:
inline void Dinic () {
maxflow = 0;
while (DinicBFS ()) maxflow += DinicDFS (s, inf);
return;
}
};
}
最小割
删去一些边,使得 \(s\) 与 \(t\) 不连通,求这些边的最小容量和。
形式化一点:
- 「割(Cut)」:将网络 \(G\) 分为 \(S\) 和 \(T = V - S\) 两个点集,满足 \(s\in S, t\in T\),则称 \((S, T)\) 为 \(G\) 的一个割。
- 「割的容量(Cut capacity)」:对于网络 \(G\) 的一个割 \((S, T)\),其容量 \(c(S, T)\) 为 \(\sum_{u \in S, v \in T, (u, v)\in E}c(u, v)\)。
- 「最小割(Min-cut)」:求一个割 \((S, T)\),使 \(c(S, T)\) 最小。
最大流最小割定理:最大流等于最小割的容量。
稍加思考还是比较好想到证明的。
跑最大流时跑满容量的边全割掉就是一个合法的割了,如果割完后图还联通就说明还有增广路,那就不是最大流了。既然这已经是一种合法的割了那最小割就不可能大于最大流。
如果最小割小于最大流,显然割掉的边是必由之路,应该割掉的边跑满了之后没有增广路了,那就不可能有更多的流流到汇点,假设不成立。
不大于也不小于就只能等于了呗。
费用流
- 「费用(Cost)」:每条边新增一个权值「费用」,即 \(1\) 单位的流经过这条边所需的费用。单位为 \(a\) 的流经过一条费用和为 \(b\) 的路径所需费用为 \(a\times b\)。
- 「最小费用最大流(Min-cost max-flow)」:满足流最大的前提下使费用最小。
EK 费用流
仍使用 EK 算法的思路,但是在求最短路的过程,边长度不再是 \(0/1\),而是费用。
注意反向边费用为负,原因考虑反向推流的过程。
ZKW 费用流
Dinic 求分层图换成 SPFA 即可。
但一个比较恶心的事情是,这样不能当前弧优化,无法保证复杂度。
但是上界依然很松,所以随便用!
一份实现:
const ll N = 1e5 + 10, inf = 1ll << 40;
namespace GRAPH {
class Edge {
public:
ll v, w, c, r;
};
class Graph {
private:
ll n, s, t;
std::vector <Edge> tu[N];
public:
inline void Init (ll _n, ll _s, ll _t) { n = _n, s = _s, t = _t; return; }
inline void AddEdge (ll u, ll v, ll w, ll c) {
ll p1 = tu[u].size (), p2 = tu[v].size ();
tu[u].push_back ((Edge) { v, w, c, p2 });
tu[v].push_back ((Edge) { u, 0, -c, p1 });
return;
}
private:
ll dis[N]; bool vis[N];
public:
ll maxflow, mincost;
private:
inline bool SPFA () {
memset (vis, 0, sizeof (vis));
memset (dis, 0x3f, sizeof (dis));
std::queue <ll> q;
q.push (s), dis[s] = 0, vis[s] = true;
while (!q.empty ()) {
ll u = q.front (); q.pop ();
far (p, tu[u]) {
if (!p.w || dis[u] + p.c >= dis[p.v]) continue;
dis[p.v] = dis[u] + p.c;
if (!vis[p.v]) q.push (p.v), vis[p.v] = 1;
}
vis[u] = false;
}
return dis[t] < inf;
}
inline ll DFS (ll u, ll flow) {
if (u == t || flow <= 0) return flow;
ll sum = 0; vis[u] = true;
far (&p, tu[u]) {
if (!p.w || dis[p.v] != dis[u] + p.c || vis[p.v]) continue;
ll k = DFS (p.v, std::min (flow, p.w));
sum += k, flow -= k;
p.w -= k, tu[p.v][p.r].w += k;
if (flow <= 0) break;
}
return sum;
}
public:
inline void Dinic () {
maxflow = mincost = 0;
while (SPFA ()) {
ll f = DFS (s, inf);
maxflow += f, mincost += f * dis[t];
}
return;
}
};
}
例题
[SCOI2007] 蜥蜴
拆点后成板子题。
[SDOI2015] 星际战争
二分时间,然后建二分图,在激光武器和巨型机器人之间连容量为无限的边。
源点到激光武器容量为时间乘攻击力,巨型机器人到汇点容量为装甲值。
如果最大流等于总装甲值说明合法。
注意精度问题,建议乘 \(10000\)。
士兵占领
最少很难求,于是转化为每个格都放了士兵之后,最多能去掉多少个士兵。
源点向代表每一行的点连边,容量为这一行最多能删除的士兵数量,列同理。
如果某一个点无障碍,则将其所属行和所属列连边。
[HNOI2007] 紧急疏散EVACUATE
二分时间,然后把一个门拆成多个门,代表不同时间。
然后就比较好想了,但是不好预处理。
[SDOI2009] 晨跑
费用流板子题。
[SDOI2016] 数字配对
比较重要的一个性质是,如果 \(a_i\) 和 \(a_j\) 可以配对,那么两者质因数个数刚好相差一。
那么可以根据质因数个数奇偶性建出二分图然后跑费用流。
[SCOI2007] 修车
发现这个费用很难计算啊。
但是我们有拆点!谁说只能拆成出入点的?
你把第 \(i\) 个师傅拆成 \(j\) 个师傅,其中的第 \(k\) 个 \(i\) 号师傅表示这个师傅倒数第 \(k\) 次修车,这个时候花费用的时间要乘 \(k\),因为后面修的 \(k-1\) 车都会被这次耽误。
然后跑一个费用流。
[NOI2012] 美食节
和修车差不多,但是交上去会发现 T 了!怎么回事呢?
点太多了。
你发现一次用不到很多点,所以你考虑动态加点,一个师傅被增广过就给他再拆一个点。
[AHOI2009] 最小割
首先根据证明最大流最小割定理的过程,可行边必须满流。
然后你发现如果残量网络中仍有 \(u\) 到 \(v\) 的路径则 \((u, v)\) 也不是可行边,因为砍了没用。
剩下都是可行边。
然后发现若残量网络 \(S\) 能到 \(u\) 且 \(v\) 能到 \(T\),那么边 \((u, v)\) 是一条必经边。
否则经过这条边的增广路径上还会有与这条边容量一样的边,割掉后效果相同。
考虑跑 Tarjan 后使用 SCC 判定连通。
标签:费用,源点,增广,ll,tu,网络,笔记,学习,复杂度 From: https://www.cnblogs.com/K8He/p/Flow.html