算法学习 / 图论
10 minutes read (About 1543 words)

网络流

玩一玩 details 标签！

内容在这里！

本文部分内容来自 OI-Wiki 相关章节

模板

Dinic 最大流（多路增广+当前弧优化）

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1205;
const int MAXM = 120005;

int n, m, s, t;

struct Edge {
    int v, nxt;
    ll w;
} edge[MAXM << 1];
int head[MAXN], cnt = 1;
int head_or[MAXN];

void AddEdge(int u, int v, ll w) {
    edge[++cnt].w = w;
    edge[cnt].v = v;
    edge[cnt].nxt = head_or[u];
    head_or[u] = cnt;
}

int d[MAXN];
bool vis[MAXN];

bool bfs() {
    memset(vis, 0, sizeof(vis));
    memcpy(head, head_or, sizeof(head));
    vis[s] = 1, d[s] = 0;
    queue<int> q;
    q.push(s);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            ll w = edge[i].w;
            if (vis[v] || (w == 0)) continue;
            vis[v] = 1;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    return vis[t];
}

ll dfs(int u, ll flow) {
    if (u == t) return flow;
    ll rest = flow;
    for (int i = head[u]; i && rest; i = edge[i].nxt) {
        head[u] = i;
        int v = edge[i].v;
        ll w = edge[i].w;
        if (w == 0 || d[v] != d[u] + 1) continue;
        ll tmp = dfs(v, min(rest, w));
        if (tmp == 0) d[v] = 0;
        edge[i].w -= tmp;
        edge[i ^ 1].w += tmp;
        rest -= tmp;
    }
    return flow - rest;
}

ll dinic() {
    ll ret = 0, tmp = 0;
    while (bfs())
        while (tmp = dfs(s, INF)) ret += tmp;
    return ret;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        AddEdge(u, v, c), AddEdge(v, u, 0);
    }
    printf("%lld", dinic());
    return 0;
}

类 Dinic 费用流

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
#include <bits/stdc++.h>
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int MAXN = 5005;
const int MAXM = 50005;

int n, m, s, t, ans;

struct Edge {
    int v, nxt, w, c;
} edge[MAXM << 1];
int head[MAXN], cnt = 1;

void AddEdge(int u, int v, int w, int c) {
    edge[++cnt].w = w;
    edge[cnt].v = v;
    edge[cnt].c = c;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int d[MAXN];
bool vis[MAXN];

bool spfa() {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    vis[s] = 1, d[s] = 0;
    queue<int> q;
    q.push(s);
    while (q.size()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            int w = edge[i].w, c = edge[i].c;
            if (w != 0 && d[u] + c < d[v]) {
                d[v] = d[u] + c;
                if (vis[v] == 0) q.push(v), vis[v] = 1;
            }
        }
    }
    return d[t] != INF;
}

int dfs(int u, int flow) {
    vis[u] = 1;
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i && rest; i = edge[i].nxt) {
        int v = edge[i].v;
        int w = edge[i].w, c = edge[i].c;
        if (vis[v] || w == 0 || d[v] != d[u] + c) continue;
        int tmp = dfs(v, min(rest, w));
        if (tmp == 0) d[v] = INF;
        edge[i].w -= tmp;
        edge[i ^ 1].w += tmp;
        rest -= tmp;
        ans += c * tmp;
    }
    vis[u] = 0;
    return flow - rest;
}

int dinic() {
    int ret = 0, tmp = 0;
    while (spfa()) {
        while (tmp = dfs(s, INF)) ret += tmp;
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &m);
    s = 1, t = n;
    for (int i = 1; i <= m; ++i) {
        int u, v, w, c;
        scanf("%d%d%d%d", &u, &v, &w, &c);
        AddEdge(u, v, w, c), AddEdge(v, u, 0, -c);
    }
    int maxflow = dinic();
    printf("%d %d", maxflow, ans);
    return 0;
}

建模方法

无源汇上下界可行流

给定无源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时每一个点流量平衡。

不妨假设每条边已经流了 $b(u,v)$ 的流量，设其为初始流。同时我们在新图中加入 u 连向 v 的流量为 $c(u,v) - b(u,v)$ 的边。考虑在新图上进行调整。

由于最大流需要满足初始流量平衡条件（最大流可以看成是下界为 0 的上下界最大流），但是构造出来的初始流很有可能不满足初始流量平衡。假设一个点初始流出流量 - 初始流入流量为 M。

若 M=0，此时流量平衡，不需要额外边。

若 M>0，此时出流量过大，需要新建附加源点 SS，SS 向其连流量为 M 的附加边。

若 M<0，此时入流量过大，需要新建附加汇点 TT，其向 TT 连流量为 -M 的附加边。

如果附加边满流，说明这一个点的流量平衡条件可以满足，否则这个点的流量平衡条件不满足。（因为附加流满足流量平衡）

在建图完毕之后跑 S 到 T 的最大流，若 S 连出去的边全部满流，则存在可行流，否则不存在。

有源汇上下界可行流

给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。

假设源点为 S，汇点为 T。

则我们可以加入一条 T 到 S 的上界 $\inf$ 下界为 0 的边转化为无源汇上下界可行流问题。

若有解，则 S 到 T 的可行流流量等于 T 到 S 的附加边的流量。

有源汇上下界最大流

给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。如果存在，询问满足标定的最大流量。

我们找到网络上的任意一个可行流。如果找不到解就可以直接结束。

否则我们考虑删去所有额外边之后的残量网络并且在网络上进行调整。

我们在残量网络上再跑一次 S 到 T 的最大流，将可行流流量和最大流流量相加即为答案。

有源汇上下界最小流

给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。如果存在，询问满足标定的最小流量。

类似的，我们考虑将残量网络中不需要的流退掉。

我们找到网络上的任意一个可行流。如果找不到解就可以直接结束。

否则我们考虑删去所有额外边之后的残量网络。

我们在残量网络上再跑一次 T 到 S 的最大流，将可行流流量减去最大流流量即为答案。

# 网络流
「随记」hexo-inject 插件的使用
「CF1295」Same GCDs

Comments

Follow

一言（ヒトコト）


    2333



Recent

Categories

Tag Cloud

0/1分数规划 2-SAT FFT/NTT KMP Pólya计数 ST算法 bitset dfs序 python set 主席树 乘法逆元 二分图 二分图匹配 二分答案 二叉堆 二维偏序 倍增 分块 前缀和 动态点分治 动态规划 单调队列 博弈论 卡特兰数 可持久化trie 后缀自动机 启发式合并 哈希(hash) 堆 复杂度分析 多项式 字符串 容斥原理 差分 差分约束系统 平衡树 异或 强连通分量 排序 搜索 数学 数学期望 数据结构 数论 最小割 最短路 最短路树 最近公共祖先 构造 栈 树上前缀和 树上差分 树套树 树形dp 树状数组 树链剖分 概率 欧拉函数 欧拉路 点分治 状态压缩 生成函数 生成树 矩阵 离散化 素数 线性基 线段树 组合数 组合计数 网络流 群论 背包 虚树 行列式 计数dp 计算几何 贪心 费用流 逆元 高斯消元
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×