网络流学习笔记

发表于

网络流

有一部分复制的这篇 博客

最大流=最小割

最小链覆盖

dag最小链覆盖 = n - 拆点跑二分图最大匹配
最小链覆盖 = 最长反链
最小反链覆盖 = 最长链

最小割

套路：

有一些限制，求满足限制之一的最优解。多选一的题可以考虑最小割

带负边权的最小割：

顾名思义就行。

sol:

先把负边都割掉，然后跑最小割。

最大权闭合子图：

一个有向图中，每个点有点权 wiw_i（可负）

现在需要找到一个子图，满足：

  • 对于所有边 (u,v)(u,v) ，点 uu 在子图中则 vv 必在子图中
  • 子图的点权和最大

这个子图就是最大权闭合子图

sol:

正点权向源点连正边，负点权向汇点连绝对值边，有边相连的点之间连无穷边

最大权闭合子图=正点权和-最小割

新图的一组割，代表原图的一个闭合子图，正点被割代表不选，负点被割代表选

最大密度子图：

给定一个无向图，要求它的一个子图，使 ∣E∣∣V∣\frac{|E|}{|V|} 最大 。

sol：

二分答案，求 ∣E∣−∣V∣x≥0|E| - |V|x \geq 0, 边的收益为 +1+1, 点的收益为 −x-x. 跑最大权闭合子图

平均值最小割：

给定一个图，源点，汇点，求一个割，使边权平均值最大。

sol：

二分平均值， 得到: val−x∣E∣≥0val - x|E| \geq 0 , 给每条边的权值减去 xx ，再跑最大流

dp\rm dp 求最小割(最大流)：

最大流=最小割

然后 $ \rm dp$ 求最小割就可以求出最小割和最大流了。

一般比较规则的图可以考虑 dp\rm dp 。

一般设 f(i)f(i) 表示考虑到了前 ii 个点。

[例题](CF724E Goods transportation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

必经边和可行边

必经边和可行边定义

必经边：

所有情况下选出的边的交

可行边：

所有情况下选出的边的并。

求二分图最大匹配必经边和可行边

求出可行边

条件

满流

对于二分图上的一条偶链（边数为偶数的链）或者一个偶环， 这个偶链或偶环上的边是可行边，因为改变偶链或偶环上被选中的边，匹配数不变。

在残量网络中跑 sccscc , 两端点都在同一 sccscc 中的边是可行边。

考虑残量网络，一条边被选，在残量网络中会有一条反向边，对于一个偶环，显然在把边的方向取反后会变成一个环。对于一条偶链，把源点考虑进去，他的两个端点，一定有一个被匹配，一个不被匹配，所以对于这条路径，源点连向一个端点，另一个端点连向源点，构成了一个环。

求出必经边

条件

  1. 满流
  2. 残余网络中两端点在不同 sccscc 中。

考虑可行但不必经的边 ：

对于二分图上的一条偶链（边数为偶数的链）或者一个偶环， 这个偶链或偶环上的边是可行但不必经边，因为改变偶链或偶环上被选中的边，匹配数不变。

在残量网络中跑 sccscc , 两端点都在同一 sccscc 中的边是可行但不必经边。

考虑残量网络，一条边被选，在残量网络中会有一条反向边，对于一个偶环，显然在把边的方向取反后会变成一个环。对于一条偶链，把源点考虑进去，他的两个端点，一定有一个被匹配，一个不被匹配，所以对于这条路径，源点连向一个端点，另一个端点连向源点，构成了一个环。

在残量网络中跑 sccscc , 两端点在不同 sccscc 中的边是必经边。

求最小割必经边和可行边

求出可行边

条件

1.满流。

2.在残余网络中找不到入点到出点的路径。

若不满流显然可以找到另一条更小的满流的限制流量的边。

若满流但在残余网络中能找到入点到出点的路径，那么需要同时割掉这条边和残余网络中路径上某条边才能实现“割”，而这两条边上的流量和一定等于其他某条或某几条满流的边的流量和，否则可以继续增广，又因为位于残余网络上的那条边一定不满流，所以这种割法不是最小割。

求法：

在残余网络中 tarjantarjan 求 SCCSCC，入出两点在同一 SCCSCC 中说明残余网络中存在入点到出点的路径。

由于该边满流，它的反向边一定存在于残余网络中，反向边与其他入点到出点的路径会构成 SCCSCC。

求出必经边

条件

1.满流。

2.残余网络中源点能到入点，出点能到汇点。

若不满流显然可以找到另一条更小的满流的限制流量的边。

若满流但在残余网络中源点不能到入点或出点不能到汇点，那么在每条单独路径上一定都存在一条满足最小割可行边的边（容量为0阻断路径且没有其他路径），割掉这条可行边是等价的。

必须边的另一种理解是扩大容量后能增大最大流的边。

求法

在残余网络上从源点开始 dfsdfs，从汇点开始反向 dfsdfs，标记到达的点，然后枚举满流边判断即可。

若求过可行边，已经有了 SCCSCC，直接判断入点是否与源点在同一 SCCSCC 中且出点是否与汇点在同一 SCCSCC 中即可。

考虑为什么两种算法是等价的，由于源点到入点一定有流，所以一定存在入点到源点的有流路径，等价得证。

费用流

费用流每增广一次，增广路至少+1。所以复杂度为 O(nmf)O(nmf) ， ff 表示流量。

套路

求最小费用流，对于一些贡献不是常数的情况 （如选 ii 个的费用为 i2i^2），如果费用递增，那么可以直接把每个费用拆成多个容量为 11, 费用不同的边 (如 1,2,3,...i1, 2, 3, ... i)。证明如下:

对于一种方案的贡献，在跑最小费用流时，一定先考虑费用更小的边，而因为费用随次数递增，所以取出的边满足是连续的一段。

[上下界流](上下界网络流 - OI Wiki (oi-wiki.org))

无源汇上下界可行流

先强制让每条边流出流量为下界的流，这样有一些点会出现流量不守恒的情况，考虑解决这个问题，把每条边的容量改为上界减下界。设一个原点 SS , 对于入流量大于出流量的点，从原点连一条容量为入流量减出流量的边,对于出流量大于入流量的点，向汇点连一条容量为出流量减入流量的边。跑最大流。

有源汇上下界可行流

从 TT 向 SS 连一条容量为无穷大的边，跑无源汇上下界可行流。 T−>ST -> S 的流量就是可行流的流量。

有源汇上下界最小流

方法1 ：先不考虑 T−>ST->S 的边，跑一遍可行流，加上 T−>ST->S 再跑一遍。

方法2 ：感性理解，先跑一遍可行流，再从 TT 向 SS 跑最大流。

有源汇上下界最大流

感性理解，先跑一遍可行流，再从 SS 向 TT 跑最大流。

有源汇上下界最小费用流

对偶图

定义：对于一张平面图（边和边的交点都是边的端点），点和边把整张图分成了一些平面，那么以平面作为点，以平面之间的公共边作为边构成的图就是原图的对偶图。

如：

img

性质：

原图的一个割对应对偶图的一个环(不规定源点和汇点)

最大流=最小割=对偶图的最短路(规定源点和汇点，连接源点和汇点后仍是平面图)

例题

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f

using namespace std;

const int N = 2e6 + 10, M = 12e6 + 10;
int head[N], nxt[M], len[M], to[M], dep[N], n, m, tot = 1;
int S, T;
priority_queue<pair<int, int> > q;
int dis[N], vis[N];

void add(int x, int y, int z)
{
  nxt[++tot] = head[x];
  head[x] = tot;
  to[tot] = y;
  len[tot] = z;
}

int id(int x, int y, int op)
{
  return op * ((n - 1) * (m - 1)) + (x - 1) * (m - 1) + y;
}

int dij(int S, int T)
{
  memset(dis, 0x3f, sizeof(dis));
  q.push(make_pair(0, S));
  dis[S] = 0;
  vis[S] = 1;
  while (q.size())
  {
    int u = q.top().second;
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = nxt[i])
    {
      int v = to[i];
      if (dis[u] + len[i] < dis[v])
      {
        dis[v] = dis[u] + len[i];
        if (!vis[v]) q.push(make_pair(-dis[v], v)), vis[v] = 1;
      }
    }
  }
  return dis[T];
}

int main()
{
  scanf("%d%d", &n, &m);
  T = 2 * n * m + 10, S = 2 * n * m + 20;
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j < m; ++j)
    {
      int x;
      scanf("%d", &x);
      if (i == 1)
      {
        add(T, id(i, j, 1), x);
        add(id(i, j, 1), T, x);
      }
      else if (i == n)
      {
        add(id(i - 1, j, 0), S, x);
        add(S, id(i - 1, j, 0), x);
      }
      else add(id(i - 1, j, 0), id(i, j, 1), x), add(id(i, j, 1), id(i - 1, j, 0), x);
    }
  }
  for (int i = 1; i < n; ++i)
  {
    for (int j = 1; j <= m; ++j)
    {
      int x;
      scanf("%d", &x);
      if (j == 1)
      {
        add(S, id(i, j, 0), x);
        add(id(i, j, 0), S, x);
      }
      else if (j == m)
      {
        add(id(i, j - 1, 1), T, x);
        add(T, id(i, j - 1, 1), x);
      }
      else add(id(i, j - 1, 1), id(i, j, 0), x), add(id(i, j, 0), id(i, j - 1, 1), x);
    }
  }
  for (int i = 1; i < n; ++i)
  {
    for (int j = 1; j < m; ++j)
    {
      int x;
      scanf("%d", &x);
      add(id(i, j, 1), id(i, j, 0), x);
      add(id(i, j, 0), id(i, j, 1), x);
    }
  }
  cout << dij(S, T);
  return 0;
}

洛谷上 dijdij 还没 dinicdinic 快

套路总结