网络流

最大流

将 $A$ 看作水源,$G$ 看作汇点,每一条边可以看作管道,每个管道有一个最大容量,每条路上有一个流量。很明显每条管道上的流量是不可能超过管道的容量的。

现在水从A源源不断的流入,那么单位时间内流过 $G$ 的最大流量是多少?


先介绍增广路的概念

增广路:一条能从起点走到汇点的路,且这条路没有满流的边。

求解最大流的过程实际上就是不断寻找增广路的过程,当图中不存在增广路时,也就意味着水流无法再增加,即已经达到最大流。

但这还存在一些问题,举例说明一下:

首先对 $(s, 1, 2, t)$ 进行增广

再对 $(s ,2 ,t)$ 进行增广

我们发现这并不是最大流,因为 $(1,t)$ 这条边没有用到。

我们希望 $(1,2)$ 这条边的流量可以退回去,然后走 $(1,t)$ 这条边。我们称这个操作称为 退流

要实现退流,需要在图中加入反向边。反向边的初始容量和流量都为0。

在进行增广的时候,如果某条边的流量增加 $x$,那么要在对应反向边的流量 减去 $x$。 这样的话反向边的流量就会出现负数的情况,我们可以理解为这条边有多少流量可以退流

以上就是求解最大流的思想,具体的实现方法有很多,接下来会介绍一些常用算法。

时间复杂度分析

可以证明最多进行 $O(nm)$ 次增广,所以想要优化时间,只能去加速找增广路的速度。如果每次增广都用 $bfs$,则总的复杂度就是 $O(nm^2)$。

Edmond—Karp

从源点 $s$ 不断的广搜(BFS),记录从 $s$ 到当前点 $i$ 的可增加的水流量 $a[i]$。 如果 $a[t] > 0$ 那么意味着有一条增广路存在,通过记录路径可以更新这条增广路上的流量。

如果直到搜索结束,$a[t]$ 还是为 $0$,则表示图中没有增广路,此时即可得到最大流。

时间复杂度为 $O(nm^2)$。

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
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 EdmonsKarp{ //时间复杂度O(v*E*E)
int n,m;
vector<Edge> edges; //边数的两倍
vector<int> G[maxn]; //邻接表,G[i][j]表示节点i的第j条边在e数组中的序号
int a[maxn]; //起点到i的可改进量
int p[maxn]; //最短路树上p的入弧编号

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(;;){
for (int i = 0; i <= n; i++) a[i] = 0;
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++){
Edge& e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow){ //!a[e.to] 是了保证不会回退和出现分叉
p[e.to] = G[x][i]; //记录边的编号
a[e.to] = min(a[x],e.cap - e.flow);
Q.push(e.to);
}
}
if(a[t]) break; //走到汇点
}
if(!a[t]) break; //没有一条增广路存在
for(int u=t;u != s;u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
};

Dinic

每次先用 $BFS$ 去构造层次图,然后在层次图上进行 $DFS$ 增广,不断重复这个过程,直到 $BFS$ 无法构建出 $s$ 到 $t$ 的层次图。

在层次图中,到源点 $s$ 的最近距离相同的点集属于同一层。每次 $DFS$ 增广时,只能从当前层次走到下一个层次,这样保证了从 $s$ 到 $t$ 最多经过 $n-1$ 层。 并且每次 $BFS$ 后,$s$ 到 $t$ 的最大距离至少会增加 $1$。因此最多增广 $n-1$ 次。一次 $DFS$ 增广的复杂度是 $O(nm)$(这里与 $EK$ 中的增广不太一样,$EK$ 中每次增广只是更新一条路径,而 $dinic$ 中每次增广是更新了所有可能的路径)。因此总复杂度为 $O(n^2m)$。

对于所有容量均为 $1$ 的图,$dinic$ 的复杂度为 $O(min(n^{\frac{2}{3}}, m^{\frac{1}{2}}) m)$。

对于二分图,$dinic$ 的复杂度为 $O(n^{\frac{1}{2}}m)$。

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
const int maxn = 1e4 + 6;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v;
int cap, flow;
Edge(int u_, int v_, int cap_, int flow_)
: u(u_), v(v_), cap(cap_), flow(flow_) {}
};

struct Dinic {
int n, m, s, t; //结点数,边数(包括反向弧),源点编号和汇点编号
vector<Edge> edges; //边表。edge[e]和edge[e^1]互为反向弧
vector<int> G[maxn]; //邻接表,G[i][j]表示节点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; //从起点到i的距离
int cur[maxn]; //当前弧下标
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
int AddEdge(int from, int to, int cap) {
edges.emplace_back(from, to, cap, 0);
edges.emplace_back(to, from, 0, 0);
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
return m - 2;
}
bool BFS() {
for (int i = 0; i <= n; ++i) vis[i] = false, d[i] = 0;
queue<int> q;
q.push(s);
d[s] = 0;
vis[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0, v; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
v = e.v;
if (!vis[v] && e.cap > e.flow) {
vis[v] = 1;
d[v] = d[x] + 1;
q.push(v);
}
}
}
return vis[t];
}
int DFS(int x, int a) {
if (x == t || a == 0) return a;
int flow = 0, f;
for (int &i = cur[x], v; i < G[x].size(); i++) { //从上次考虑的弧
Edge& e = edges[G[x][i]];
v = e.v;
if (d[x] + 1 == d[v] && (f = DFS(v, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s, this->t = t;
int flow = 0;
while (BFS()) {
for (int i = 0; i <= n; i++) cur[i] = 0;
flow += DFS(s, INF);
}
return flow;
}

int edge_id[maxn]; // 每条边的编号
vector<int> cut; // 割边的编号
void findCut(int m) {
cut.clear();
for (int i = 0; i <= n; i++) vis[i] = 0;
queue<int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &id : G[u]) {
auto &e = edges[id];
if (!vis[e.v] && e.cap > e.flow) {
vis[e.v] = 1;
q.push(e.v);
}
}
}
for (int i = 0; i < m; i++) {
auto &e = edges[edge_id[i]];
if (vis[e.u] == vis[e.v]) continue;
if (e.cap == e.flow) cut.push_back(i + 1); // 1-index
}
}
};

ISAP

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
const int maxn = "Edit";
struct ISAP {
int n, m, s, t; //结点数,边数(包括反向弧),源点编号和汇点编号
vector<Edge> edges; //边表。edges[e]和edges[e^1]互为反向弧
vector<int> G[maxn]; //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; //起点到i的距离
int cur[maxn]; //当前弧下标
int p[maxn]; //可增广路上的一条弧
int num[maxn]; //距离标号计数
void init(int n) {
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.emplace_back(from, to, cap, 0);
edges.emplace_back(to, from, 0, 0);
int m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int Augumemt() {
int x = t, a = INF;
while (x != s) {
Edge& e = edges[p[x]];
a = min(a, e.cap - e.flow);
x = edges[p[x]].from;
}
x = t;
while (x != s) {
edges[p[x]].flow += a;
edges[p[x] ^ 1].flow -= a;
x = edges[p[x]].from;
}
return a;
}
void BFS() {
for (int i = 0; i <= n; i++) vis[i] = 0;
for (int i = 0; i <= n; i++) d[i] = 0;
queue<int> q;
q.push(t);
d[t] = 0;
vis[t] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
int len = G[x].size();
for (int i = 0; i < len; i++) {
Edge& e = edges[G[x][i] ^ 1];
if (!vis[e.from] && e.cap > e.flow) {
vis[e.from] = 1;
d[e.from] = d[x] + 1;
q.push(e.from);
}
}
}
}
int Maxflow(int s, int t) {
this->s = s;
this->t = t;
int flow = 0;
BFS();
for (int i = 0; i <= n; i++) num[i] = 0;
for (int i = 0; i < n; i++)
if (d[i] < INF) num[d[i]]++;
int x = s;
for (int i = 0; i <= n; i++) cur[i] = 0;
while (d[s] < n) {
if (x == t) {
flow += Augumemt();
x = s;
}
int ok = 0;
for (int i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (e.cap > e.flow && d[x] == d[e.to] + 1) {
ok = 1;
p[e.to] = G[x][i];
cur[x] = i;
x = e.to;
break;
}
}
if (!ok) // Retreat
{
int m = n - 1;
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (e.cap > e.flow) m = min(m, d[e.to]);
}
if (--num[d[x]] == 0) break; // gap优化
num[d[x] = m + 1]++;
cur[x] = 0;
if (x != s) x = edges[p[x]].from;
}
}
return flow;
}
};

最小费用最大流

思想

最小费最大流问题是指:在每条边都有一个权值的时候,使得流量最大时候,权值和最小。

注意这里的费用(可改进量)指的是单位流量的费用。

注意图中可以存在负边,但不能存在负圈。

模板

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
struct Edge{
int from,to,cap,flow,cost;
Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w) {}
};

struct MCMF{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn]; //是否在队列中
int d[maxn]; //bellmanford 到源点距离
int p[maxn]; //上一条弧
int a[maxn]; //可改进量

void init(int n){
this-> n = n;
for(int i=0;i<=n;i++) G[i].clear();
edges.clear();
}

void AddEdge(int from,int to,int cap,int cost){
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}

bool BellmanFord(int s,int t,int& flow,ll& cost){
for(int i=0;i<=n;i++) d[i] = INF;
for (int i = 0; i <= n; i++) inq[i] = 0;
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i=0;i<G[u].size();i++){
Edge& e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u] + e.cost){
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if(!inq[e.to]) {Q.push(e.to); inq[e.to] = 1;}
}
}
}
if(d[t] == INF) return false; // 当没有可增广的路时退出
flow += a[t];
cost += (ll)d[t] * (ll)a[t];
for(int u=t; u!= s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
return true;
}

int MincostMaxflow(int s,int t,ll& cost){
int flow = 0; cost = 0;
while(BellmanFord(s,t,flow,cost));
return flow;
}
};

经典建图

无源汇可行流(循环流)

每条边的流量都有个上下界,并且每个点都要满足流量平衡,所以这一定是一个循环流。

做法

建立附加源点 $ss$,附加汇点 $tt$。

初始假设每条边都已经有了下界的流量,但这样可能会使得流量不平衡。因此我们需要调整一下流量,使得每个点都满足流量平衡的要求。

建立残余网络,因为默认了每条边都已经拥有了下界的流量,所以每条边的上下界就由 $[low, high]$ 变为了 $[0, high - low]$。

设 $a[i]$ 表示 $i$ 点流入的流量与流出的流量之差。

  • 对于 $a[i] > 0$,建立 $(ss, i)$ 容量为 $a[i]$ 的边。

$a[i] > 0$ 表示 $i$ 点流入的流量多于流出的流量,那我们需要在残余网络上表示出来这个多余的流量,因此建立 $(ss,i)$ 的边,表示 $i$ 点会多进入一些流量。如果最后这个边可以跑满,说明多余的流量可以找到出路,从而可以达到流量平衡。

  • 对于 $a[i] < 0$, 建立 $(i,tt)$ 容量为 $-a[i]$ 的边

同理。

  • 对于原图中的边 $(u, v, low, high)$,建立 $(u,v)$ 容量为 $high - low$ 的边。

原因在上面说过了。

  • 跑 $ss$ 到 $tt$ 的最大流,如果从 $ss$ 出去的边(进入 $tt$ 的边)全部满流,则证明有解,否则无解。

因为这些从 $ss$ 出去的边,都是那些原图中导致了流量不平衡的流量,只有修正了这些流量,才能使得原图流量平衡。

最后每条边的实际流量 = 下界 + 残余网络上的流量

一道模板题:zoj 2314

有源汇可行流

每条边的流量都有个上下界,并且除了源点和汇点之外每个点都要满足流量平衡

做法

  • 设源点为 $s$,汇点为 $t$。

  • 建立一条 $(t,s)$ 容量为无穷大的边。

  • 再按照无源汇可行流的方式建图。

  • 跑 $ss$ 到 $tt$ 的最大流,如果从 $ss$ 出去的边(进入 $tt$ 的边)全部满流,则证明有解,否则无解。

有源汇之后,原图就不满足流量平衡了,因为源点和汇点不满足流量平衡。但是因为从源点出发的总流量等于到达汇点的总流量,因此我们可以建立一条 $(t,s)$ 容量为无穷大的边,这样到达汇点的流量就会再流回到源点,从而达到了流量平衡。

最后 $(t,s)$ 这条边的流量就是原图的可行流

因为建边的时候,$(s,tt)$ 这条边的上界就是所有从 $s$ 点出发的流量的下界。

有源汇上下界最大流

每条边的流量都有个上下界,并且除了源点和汇点之外每个点都要满足流量平衡,并且希望总流量尽可能的大。

做法

  • 按照有源汇可行流的方式建图。

  • 跑 $ss$ 到 $tt$ 的最大流,如果从 $ss$ 出去的边(进入 $tt$ 的边)全部满流,则证明有解,否则无解。

  • 再跑 $s$ 到 $t$ 的最大流,得到的流量即为答案。

如何使可行流变为最大流呢

因为每条边的下界都已经满足了,要使得流最大,就要使得残余网络上的流最大。 因此只要跑 $s$ 到 $t$ 的最大流即可。

那么问题来了:

  • 会不会有的边退流之后就不满足最后的流量平衡了?

不会的,因为退流的操作实际上是:如果现在退流到 $p$ 点,那么 $p$ 点需要去找新的路径到达汇点,如果能找到则退流成功,否则退流失败。从结果上看,从 $p$ 点出去的流量并没有改变,因此不会有问题。

  • 是否需要去掉源点汇点和 $(t,s)$ 这条边?

实际上不需要去掉附加源点和附加汇点,因为这两个点所连接的边都已经满流了,并且它们都是单向边,因此再次跑 $s$ 到 $t$ 的最大流时附加源汇不会产生任何影响。

也不需要去掉 $(t,s)$ 这条反向边,因为这条边的流量会退回去。跑完 $ss$ 到 $tt$ 的最大流之后,这条边的流量实际上是满足下界的可行流。当我们再次跑 $s$ 到 $t$ 的最大流的时候这条边的流量会退回去,即也会算到答案中,因此不必去掉这条反向边。

一道模板题:zoj 3229

有源汇上下界最小流

每条边的流量都有个上下界,并且除了源点和汇点之外每个点都要满足流量平衡,并且希望总流量尽可能的小。

做法

  • 按照无源汇可行流进行建图
  • 跑 $ss$ 到 $tt$ 的最大流
  • 建立 $(t,s)$
  • 再跑 $ss$ 到 $tt$ 的最大流,$(t,s)$ 这条边上的流量就是答案

为什么有源汇可行流跑出来的不是最小流

如图所示

没有写出来的上下界默认为 $[0, inf]$

建立残余网络

跑 $ss$ 到 $tt$ 的最大流

可以发现 $(t,s)$ 这条边上的流量是 $5$,也就代表了可行流的大小。但从原图中可以看出,实际上最小的可行流是 $3$。

问题出在哪里呢?

$1$ 号点本可以直接走到 $2$ 点然后到达 $tt$ 点,但是它却经过了 $(t,s)$ 这条边绕了一圈才到 $tt$ 点。然而 $(t,s)$ 这条边的流量表示的是最后可行流的大小,所以想要获得最小流,那么应该让通过 $(t,s)$ 边的流量尽可能地少。

因此我们先不加 $(t,s)$ 这条边,跑一次 $ss$ 到 $tt$ 的最大流,目的就是使那些可以不经过 $(t,s)$ 就可以到达 $tt$ 点的流先流满。然后再加上 $(t,s)$ ,再跑一次 $ss$ 到 $tt$ 的最大流,得到的 $(t,s)$ 边的流量就是答案。

无解的情况还是和上面一样的判断。

一道模板题:uva 1440

无(有)源汇上下界费用流

建图方式与对应的可行流是相同的,连接附加源汇的边的费用为 $0$。

最小割

在有向图 $G$ 中,每条边都有一个权值,有源点 $s$,汇点 $t$。要使得 $s$ 和 $t$ 不连通,所需要去掉的边的集合称为 $G$ 的一个。在所有的中,权值和最小的称为最小割

定理最大流 = 最小割

考虑每条从 $s$ 到 $t$ 的流,如果选择割边,那么一定是选这条路上满流的一条边(瓶颈边)。最大流找出了所有的增广路,那么只要切掉每条增广路上的瓶颈边即可,最后割边的总权值就是最大流(因为瓶颈边的流量和权值(容量)相同)。

输出方案

满流的边不一定是割边!

考虑最小割是把 $s$ 和 $t$ 分成了两个不相交的点集。

因此我们可以从 $s$ 点出发,只走未满流的边,走到的点记 $vis[i] = 1$。

那么对于所有访问过的点 $(vis[i] = 1)$,如果他有一条满流的边连向为未访问过的点,则这条边就是割边。

一道模板题: hdu 3251

最大权闭合子图

闭合子图:有向图 $G$ 中,称点集 $V$ 是 $G$ 的闭合子图,当且仅当从点集 $V$ 中出发的边的终点都在点集 $V$ 中,即 $V$ 中的所有后继都在 $V$ 中。

最大权闭合子图:每个点都有一个权值(必须有负数,没有负数的话直接全选),所选的闭合子图中点权和最大,可以不选。

做法

  • $s$ 向所有正权点连边,容量为权值。
  • 所有负权点向 $t$ 连边,容量为权值的绝对值。
  • 其他的边正常连,容量为正无穷。
  • 跑 $s$ 到 $t$ 的最大流,答案为所有正权点的权值和减去最大流。

可以先贪心地把所有的正权点都选上,因为有些正权点的后继中既包含负权点也包含正权点,因此要么我们就把那些负权点选上,要么我就丢弃一些正权点。即我们的答案要不然就是减去一些正权点,要么就是减去一些负权点的绝对值。我们当然希望减去的东西越小越好。这个问题可以转化为一个最小割的模型。

按照上面的建图方式,大致可以分三种情况:

第一种

跑完最大流(最小割)之后,可以看到流量是 $3$,表示要选上这些负权点,这些负权点的影响是 $3$。

第二种

对于这张图,跑完最大流(最小割)之后流量是 $5$,表示这个正权点要去掉,他的影响是 $5$。

第三种

图中存在反向边,但实际上反向边并不会影响结果。

对于那些没有依赖关系的正权点,是不会割到的(即不会丢弃)。

对于那些没有依赖关系的负权点,也是不会割到的(即不会选)。

输出方案

割边只可能是那些连接着源点或汇点的边,因为其他边的容量都是正无穷。

连接源点的割边就是要舍弃的正权点,连接汇点的割边就是要加入的负权点

一道模板题:洛谷 2762

推广

其实这种建图方式可以解决一类问题:

每个点都有个权值,现在我可以选择某些点,使得权值和最大。 但是某些点之间可能存在直接或间接的依赖关系,因此选择某个点之后,可能某些点就无法选择了,或者某些点就必须要选择。

这种类型的都可以使用 最大权闭合子图 的建图方式,只不过中间的边的容量可能不是正无穷。

割边的意义根据题意来表示,不过无非就是选或不选。

例题:hdu 3251

最大密度子图

定义一个无向图 $G = (V,E)$ 的密度 $D$ 为该图的边数与点数的比值。

$$D = \frac{|E|}{|V|}$$

做法

这实际上是一个分数规划问题。我们二分答案 $g$

设 $h(g) = max {|E’| - |V’| \times g } $

1
2
h(g) < 0  ->  g > D
h(g) > 0 -> g < D

求解 $h(g)$ 的问题可以转化为求最大闭合子图。

二分的精度为 $eps = \frac{1}{n\times n}$。

二分的上下界为 $[0,|E|]$。

  • 源点向每条边建立容量为 $1$ 的边。
  • 每条边向其两个顶点建立无穷大的边。
  • 每个顶点向汇点建立容量为 $g$ 的边。
  • 跑 $s$ 到 $t$ 的最大流,答案为 $|E| - flow$。

割边中连接着源点的是不选的边,连接着汇点的是要选的点

拆点与拆边

朴素的拆点与拆边可以用来保证该点(边)经过不超过 $k$ 次,即节点(边)容量。

还有一种是类似多重背包的拆点(边)。

拆点

例题

二维网格图上,有 $n$ 个交点上有人。你从基地出发,想要把这 $n$ 个人接回基地,但是你的车最多一次坐两个人。问最少的距离把这n个人接回基地? $n \leq 24$


因为一次最多接两个人,那么我们可以枚举所有的两人组合。从 $s$ 向每个两人组合连边,容量为 $1$,权值为接回来的距离。然后限制每个人只能接一次,就要把这 $n$ 个人拆点,中间建一条容量为 $1$ 费用为 $0$ 的边。最后每个两人组合 向 其所影响的两个人连边。(还有可能每次只接一个人)

拆边

例题

$n$ 个城市,$m$ 条有向路,现在要运送 $k$ 个货物从 $1$ 号城市到 $n$ 号城市。每条路有个系数 $a_i$,和一个流量上限 $c_i$,运送 $x$ 个货物的花费为 $a_ix^2$。现在求运送完成的最小花费。

$c_i \leq 5$


因为花费不是线性的,所以没有办法表示单位流量费用。但我们注意到一条路最多运送5个货物,因此我们可以将费用拆开来建边。即拆成:$a,3a,5a,7a,9a$ 这样的费用。

区间模型

区间K覆盖

给定 $n$ 个开区间 $(a_i,b_i)$,每个区间有个权值 $w_i$,每个数字最多被覆盖 $k$ 次。问最大价值?


数轴上相邻点的容量为 $k$,费用为 $0$。$a_i$ 到 $b_i$ 的容量为 $1$,价值为$-w_i$。跑一遍最小费用最大流即可。

对于点数多,区间少的情况可以离散化。

模板题 poj3680