1、定义

可行流

设f(u,v)表示边(u,v)的当前容量上限

设c(u,v)表示边(u,v)的最大容量上限

如果网络流图中的流量满足

  • 源点S：流出量=流量总量
  • 汇点T：流入量=流量总量
  • 任意边(u,v)：0<=f(u,v)<=c(u,v)

则称该流为一个可行流

增广

增加一条路径的流量，即减少这条路径的当前流量上限，即f(u,v)的值

增广是我们求解最大流的基础

最大流

在所有可行流中流量最大的流

2、模板

EK算法

maxFlowEK返回值即为网络中最大值，cap数组中原边的逆边即为每个边的流量。

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
int cap[maxMN][maxMN];
int pre[maxMN], flow[maxMN];
void maxFlowInit(){
    memset(cap,0,sizeof(cap));
    memset(flow,0,sizeof(flow));
}
int maxFlowEKBFS(int from, int to){
    queue<int> q;
    int i;
    memset(pre,-1,sizeof(pre));
    pre[from] = 0;
    flow[from] = maxCap;
    q.push(from);
    while(!q.empty())
    {
        int id = q.front();
        q.pop();
        if(id == to)    break;
        for(i = 0 ; i <= superTo; i++){
            if(i != from && cap[id][i]>0 && pre[i] == -1){
                pre[i] = id;
                flow[i] = min(cap[id][i], flow[id]);
                q.push(i);
            }
        }
    }
    if(pre[to] == -1)   return -1;
    else    return flow[to];
}
int maxFlowEK(int from, int to){
    int ins = 0, resMaxFlow = 0;
    while((ins = maxFlowEKBFS(from, to)) != -1){
        int tmp = to;
        while(tmp != from){
            int last = pre[tmp];
            cap[last][tmp] -= ins;
            cap[tmp][last] += ins;
            tmp = last;
        }
        resMaxFlow += ins;
    }
    return resMaxFlow;
}
Dinic算法

当前弧优化版本。

maxFlowDinic返回值即为网络中最大值，edge数组中原边的逆边即为每个边的流量，每个边的下一个边即为逆边。

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
struct Node{
    int from, to, cap;
}edge[maxMN * maxMN << 1];
int cur[maxMN * maxMN << 1], dep[maxMN * maxMN << 1], que[maxMN * maxMN << 1], cnt = 0;
void maxFlowDinicInit(){
    cnt = 0;
    memset(pre, -1, sizeof(pre));
}
void addEdge(int from, int to, int cap){
    edge[cnt].from = to;
    edge[cnt].to = pre[from];
    edge[cnt].cap = cap;
    pre[from] = cnt++;
    edge[cnt].from = from;
    edge[cnt].to = pre[to];
    edge[cnt].cap = 0;
    pre[to] = cnt++;
}
bool maxFlowDinicBFS(){
    memset(dep, 0, sizeof(dep));
    dep[superFrom] = 1;
    int le = 0, ri = 1;
    que[++le] = superFrom;
    while(le <= ri){
        int now = que[le++];
        for(int iq = pre[now]; iq != -1; iq = edge[iq].to)
            if(!dep[edge[iq].from] && edge[iq].cap){
                dep[edge[iq].from] = dep[now] + 1;
                que[++ri] = edge[iq].from;
                if(edge[iq].from == superTo)    return true;
            }
    }
    return dep[superTo];
}
int maxFlowDinicDFS(int now, int flow){
    if(now == superTo)  return flow;
    int sumFlow = 0;
    for(int iq = pre[now]; iq != -1; iq = edge[iq].to){
        if(dep[edge[iq].from] == dep[now] + 1 && edge[iq].cap){
            int ins = maxFlowDinicDFS(edge[iq].from, min(flow, edge[iq].cap));
            edge[iq].cap -= ins;
            edge[iq ^ 1].cap += ins;
            sumFlow += ins;
            flow -= ins;
            if(flow <= 0)    break;
        }
    }
    return sumFlow;
}
int maxFlowDinic(){
    int maxFlow = 0;
    while(maxFlowDinicBFS()){
        memcpy(cur, pre, sizeof(pre));
        maxFlow += maxFlowDinicDFS(superFrom, 2 * maxCap);
    }
    return maxFlow;
}

3、总结

可以解决很多网络上流量分配，聚类等问题。问题的关键在于如何建图，对于多源点多汇点的图可以添加超源和超汇进行解决。EK算法时间复杂度$O(nm^2)$，Dinic算法的时间复杂度$O(mn^2)$，可以根据图的稀疏程度选取对应算法。