网络流

定义

在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[t] != 0;
}

int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int di = dfs(edges[i].to, min(flow, edges[i].weight));
            if (di > 0)
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
        }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(s, INF))
            ans += di;
    }
    return ans;
}

最小割

删除流量和最小的边集使得 S 与 T 不连通,就叫做最小割。最小割等于最大流

例题:[USACO2007 OPEN]吃饭 Dining

费用流 – SPFA + DFS

概念:在最大流的情况下求得最小的费用。其实可以直接 SPFA + Dinic 就行了,先找到一条最短路,然后再求该路径上的最大流,然后可以保证最大流的情况下求得最小费用。

bool bfs()
{
    memset(dist, 0x3f, sizeof(dist)), memset(flow, 0x3f, sizeof(flow));
    memset(vis, false, sizeof(vis)), memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(st), dist[st] = 0, vis[st] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dist[edges[i].to] > dist[u] + edges[i].cost)
            {
                dist[edges[i].to] = dist[u] + edges[i].cost;
                pre[edges[i].to] = i, flow[edges[i].to] = min(edges[i].weight, flow[u]);
                if (!vis[edges[i].to])
                    vis[edges[i].to] = true, q.push(edges[i].to);
            }
    }
    return pre[ed] != -1;
}

long long mfmc()
{
    long long tot_cost = 0, tot_flow = 0;
    while (bfs())
    {
        tot_flow += flow[ed], tot_cost += 1LL * flow[ed] * dist[ed];
        int p = ed;
        while (p != st)
        {
            int i = pre[p];
            edges[i].weight -= flow[ed], edges[i ^ 1].weight += flow[ed];
            p = edges[i ^ 1].to;
        }
    }
    return tot_cost;
}

网络流经典模型

最大权闭合子图

例题(来自于网络流 24 题):https://loj.ac/problem/6001

这一类模型主要就是建立一个依赖关系的有向图,一般分为两个部分:正权部分和负权部分。一般求其权最大的闭合子图。

一篇非常好的博客文章让我快速的理解了这个神仙玩意,大家可以去看一下。这个东西简单来讲就是在原先的基础上加源点和汇点,然后把点权转换成边权,转而求最小割、也就是最大流。如果正权满流了,那么就是要去掉这一个计划;如果是负权满流了,那么就是要在原图中割掉这条边。

题解:LOJ6001:「网络流 24 题」太空飞行计划题解

「等待时间叠加」模型

经典的例题:[SCOI2007]修车

首先,\(n\)个车主可以把整个时间分为\(n\)个时间段,然后每一个时间段的工人其实是不一样的,所以拆成\(n * m\)个点,每个点流经的上界都是\(1\),且费用都按当前次序乘上权值即可。

相似的题目还有 NOI 美食节一题。

二分图最小点权覆盖

例题:POJ 2125

考虑将一个点拆成两个:一个入点,一个出点。入点和出点分开之后,源点连\(w_-\)的权,汇点连上\(w_+\)的权。当一条边满流,说明走过了中间的入点,亦而反之即可搞定这道题。

// POJ2125.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int MAX_N = 2e5 + 200, INF = 0x3f3f3f3f;

using namespace std;

int n, m, head[MAX_N], current, dep[MAX_N], cur[MAX_N], st, ed;
bool mark[MAX_N];

struct edge
{
    int to, nxt, flow;
} edges[MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].flow = weight, head[src] = current++;
}

void addtube(int src, int dst, int flow)
{
    addpath(src, dst, flow);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    dep[st] = 1;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].flow > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[ed] != 0;
}

int dfs(int u, int flw)
{
    if (u == ed || flw == 0)
        return flw;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].flow > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int di = dfs(edges[i].to, min(flw, edges[i].flow));
            if (di > 0)
            {
                edges[i].flow -= di, edges[i ^ 1].flow += di;
                return di;
            }
        }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(st, INF))
            ans += di;
    }
    return ans;
}

void dfs_helper(int u)
{
    mark[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].flow > 0 && !mark[edges[i].to])
            dfs_helper(edges[i].to);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m), st = (n << 1) | 1, ed = st + 1;
    for (int i = 1, tmpy; i <= n; i++)
        scanf("%d", &tmpy), addtube(i + n, ed, tmpy);
    for (int i = 1, tmpx; i <= n; i++)
        scanf("%d", &tmpx), addtube(st, i, tmpx);
    for (int i = 1, tmpx, tmpy; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addtube(tmpx, tmpy + n, INF);
    printf("%d\n", dinic());
    dfs_helper(st);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!mark[i])
            ans++;
    for (int i = n + 1; i <= 2 * n; i++)
        if (mark[i])
            ans++;
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++)
        if (!mark[i])
            printf("%d -\n", i);
    for (int i = n + 1; i <= 2 * n; i++)
        if (mark[i])
            printf("%d +\n", i - n);
    return 0;
}

有上下界的网络流

无源汇的上下界可行流

问题描述

给定一个网络,每一条边的流量都要满足在区间\([lower[e_x], upper[e_x]]\)中,求一种可行的流量。

解决方案

考虑把每一条边的区间进行化简,变成\([0, upper[e_x] – lower[e_x]]\)就变成了一个正常的网络流模型了。但是,因为每一条边的下限和上限都有所不同,所以如果直接求最大流,会出现一种情况:某些边满流之后,某些边的下限不够低而导致于题意不符合。所以,我们需要处理一个数组\(di[u]\),代表需要补充或者是放出的流量,所以可知:

\[ di_u = \sum_{e = E(?, u)} e.flow – \sum_{e = E(u, ?)} e.flow \]

对于\(di_u > 0\)的情况下,考虑将超级源点\(S\)连接到\(u\),来补充所需要的流量;对于\(di_u < 0\)的情况下,考虑将点\(u\)连至超级汇点,来放出多余的流量。所以,就很显然可以解决了。

有源的上下界可行流

问题描述

给定一个网络,每一条边的流量都要满足在区间\([lower[e_x], upper[e_x]]\)中,且给定源点汇点\(s\)与\(t\),流入源点的流等于流出汇点的流,求一种可行的流量。

解决方法

加一条边:从\(t\)到\(s\),范围\([0, +\infty]\)就可以了。
注释  题目的意思其实就是忽略\(s\)与\(t\)之间的「收支平衡」。所以,直接连一条这样的边过去就好了。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注