网络流/费用流

【流模型】
如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径,我们也可以将一个有向图看作一个网流络来解决另一类型的问题。网络流比较适合用来模拟液体流经管道、 电流在电路网络中的运动、 信息网络中信息的传递等等类似的过程。
我们可以将网络流类比成水流, 如下图给出一个有向图 G =(V, E).图中的边可以想象成管道, 顶点则是管道的连接点。 边上的权值我们称之为这条边的流量上限, 可以把它想象成这条管道能通过的水流的多少。 对于图中每条边e我们记它的流量上限为 c(e) .

【最大流模型】
对于有源点s和汇点t的图,则称为网络流图。在这样的图中,源点入度为 0 且可以产生无穷大的流量,汇点出度为 0 且可以吸
收无穷大的流量。
称一条从源点到汇点的,并使除源汇之外所有结点满足流量平衡,所有边满足流量约束的流方案为有源汇网络的可行流。(这里的流方案并不一定只沿一条路流,也可能在多个结点上出现支路,但要保证满足流量约束与流量平衡条件。)
最大的可行流方案为最大流。求解最大流的问题称为最大流问题。

【求解最大流/Dinic算法】
Dinic 算法的主要思想就是每次寻找最短的增广路,并沿着它增广。因为最短增广路的长度在增广过程中始终不会变短,所以无需每次都通过广搜来寻找最短增广路。我们可以先进行一次广搜,然后考虑由近距离顶点指向远距离顶点的边所组成的分层图,在上面进行深搜寻找最短增广路(这里一次深搜就可以完成多次增广的工作)。每增广一条边,就要在其反向边上加上流入的流量,在这条边上减去流入的流量,这样,在找到一条更优的增广路后,便可以直接从反向边进行修改。
如果在分层图上找不到新的增广路了(此时我们得到了分层图所对应的阻塞流),则说明最短增广路的长度变长了或不存在增广路了,于是重新构造新的分层图。
注: 建边时一般从2开始建,这样便于正、反边的互换,只要(^1)便能得到另一条边。
构建分层图的代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;

int bfs()  {
    int v, now;
    for (int i = s;i <= t; i++) cnt[i] = en[i], dir[i] = -1;
    dir[s] = 0;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())  {
        for (int e = en[now = q.front()]; e ; e = next[e])
            if (val[e] > 0 && dir[v = gt[e]] == -1)  {
                dir[v] = dir[now] + 1;
                q.push(v);
                if (v == t) return 1;
            }
        q.pop();
    }
    return 0;
}

Dinic代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Dinic(int u, int flow)  {
    if (u == t) return flow;
    int acc = 0, v, del;
    for (int &e = cnt[u]; e ; e = next[e])  
        if (val[e] > 0 && dir[u] + 1 == dir[v = gt[e]] && dir[v] > 0)  {
            del = Dinic(v, min(val[e], flow - acc));
            if (del)  {
                val[e] -= del;
                val[e ^ 1] += del;
                acc += del;
                if (acc == flow) break;
            }
        }
    if (acc != flow) dir[u] = -1;
    return acc;
}

【费用流】
费用流则是在网络流的基础上给每条边多加了个属性,即单位流量的费用,一般在费用流的可行方案中,要求费用与流量平衡。
注意到,在网络流的求解中,每次都是随便选取一条边来进行增广,费用流中由于边多了一个权值,选边的顺序就需要确定了。显而易见,可以贪心地在残余网络上选最小费用的路径进行增广。多了个权值,在建边时反向边的权值便是负值,所以不能Dijkstra来求最小值,要用队列优化的 Bellman-Ford 算法。
实际上,费用流与网络流的差别也就在选取边的顺序上;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
queue<int> q;

int spfa()  {
    memset(vis, 0, sizeof vis);
    for (int i = 1;i <= 2 * N; i++) dir[i] = INF;
    int nxt, now;
    dir[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())  {
        vis[now = q.front()] = 0;
        for (int e = beg[now]; e ;e = next[e])
            if (cap[e] > 0 && dir[now] + cost[e] < dir[nxt = gt[e]])  {
                dir[nxt] = dir[now] + cost[e];
                if (!vis[nxt])  {
                    vis[nxt] = 1;
                    q.push(nxt);
                }
            }
            q.pop();
    }
    if (dir[t] < INF) return 1;
    return 0;
}

【网络流题目】(两题代码相同)

【POJ】2186Popular Cows

【QZYZ】1238草地排水

继续阅读网络流/费用流