网络流

关于网络流

这个东西吧，博大精深，有的题你看着像dp，或者像膜你题，但是又怎么想都想不出来，最后看算法tag发现这玩意竟然是网络流¿

网络流这一部分跟线性规划关系很大，其实图论的题基本都是dp，每个点就是状态，每个边就是状态转移的路线

最大流

网络流的模型可以抽象为水管，有一个水源，n-2个中转站，一个要送去水的目的地，每个站点都有若干个水管与其他站点相连，但是水管有粗细，每秒能通过的最大流量也不一样，求目的地每秒最多接收到多少流量。

其中，水管和中转站就是网，水流就是流，我们就得到了网络流（，上面求的就是源点到汇点的最大流。

给出一张非常经典的图：

这个图很容易看出来最大流走 1->2->4 和 1->3->4 ，最大流为 。

对于程序实现，我们只知道边的最大流量还不行，还得知道现在这条边能再承受多少流量，即剩下的流量，这个剩下的流量就叫做 残量，由边的残量构成的图就叫 残量图，如果残量为 ，那么就相当于一条断边。

在残量图上，如果我们从源点开始沿着某一条路径到达了汇点，说明这一条路上的流量还可以增加，我们就把这条路叫做 增广路。

如上图，我们可以从 开始 dfs，假设我们 dfs 到的结果是 1->2->3->4 ，我们就得到了这条增广路，将其每条边都减去流量 ，我们就得到了一个残量图：

但是此时已经没有增广路了，跟我们预期的结果不一样，我们发现，是因为程序走了 2->3 这条边抢了其他增广路的流量，我们怎么解决这个问题呢？有两个方法：

  1. 写个AI，深度学习一手，拿个数据生成器就往AI里跑，然后调AI，最后调成不会走错误路线的超级AI，自动暴切网络流

  2. 考虑实际情况，我们是OI选手，我们需要一个在考场上能用的解决方案，所以我们需要让程序在走错边时可以反悔，但又不能仅仅只是反悔，因为上图中 3->4 也是答案的一部分，如果走错边就反悔的话会 T 飞，我们得想办法只把 2->3 这条边反悔，这时就需要引入反向边了。

首先，这个反向边不只是单单建个边就完事了，我们的目的是让程序反悔，让程序跑到 时再跑回 让错误路径中 2->3 这部分浪费掉的流量给要回来，所以我们这么处理反向边：

设原边的最大容量为 maxflow , 正边的残量为 flow ，反边的残量为 rflow ，则有 flow + rflow = maxflow ，通俗来讲就是把正边流走的流量加到反边上去而不是直接消失，正反边的流量和为原最大容量

设某一条增广路的流量为 ，则对于这条增广路上的每个边，都有 flow -= a ， rflow += a ，感性理解一下，这条反向边就是为了防止走错，把正向边走的流量转移到反向边上去，再走反向边时就相当于反悔

我们有了反向边之后，上面那张图就变成了这样：

对这个图继续寻找增广路，我们就可以找到 1->3->2->4 这条增广路，最终答案为 ，与正确答案一样。

为什么这样就是对的呢？因为作了反向边处理之后，我们没走 2->3 这条路，分析一下这两条增广路：1->2->3->4， 1->3->2->4 ，我们把每一条边都拆出来，发现走了一个 2->3 和一个 3->2 ，就相当于没走，把剩下的边拼一块，我们就得到了 1->2->4 和 1->3->4 ，即得到了正确答案

有一条很显然的结论：当网络图中没有增广路时，此时的流就是最大流

证明吧…大概就是没有增广路之后我们无法反悔任何一条边来获取更大流量，所以已经是最大流了

严谨的证明请自己去bdfs论文，我太菜了只能这么解释XD

这里的反向边的实现不需要很复杂，我们可以利用成对边的思想，将链式前向星中数组下标从2开始，这样 i^1 就可以得到与 i 成对的那条边，即反边

Edmonds-Karp算法

但是有了反向边又有了一个问题：我们需要保证程序不犯傻，别走了 1->2 再走 2->1 搁这原地tp。解决办法也很简单，我们可以进行bfs，走过的点标记一遍，保证不会反着走，并计算流量和前驱，直到走到汇点或者图上无增广路为止。

这个每次bfs找一条增广路进行增广的算法就是Edmonds-Karp(EK)算法

Code: EK

EK算法的最坏时间复杂度为 ，但一般使用达不到这个上界，大概能解决 级别的网络

Dinic算法

但是我们发现，EK算法每次bfs最坏要遍历一遍整个图，最终却只找到一条最短增广路，这样效率很低，有很大优化空间

我们每次bfs时，其实可以计算出 条增广路，我们可以用dfs进行多路增广

具体方法是：每次bfs时计算出图上每个点的深度，然后从源点开始dfs，按着深度进行增广，把当前计算出的增广路全部增广掉

其实就是计算出深度，从源点开始灌水，把能灌的路径灌完再进行下一次bfs，这样我们可以大大减少bfs遍历图的次数，提高不少效率

这样每次一个bfs和一个dfs进行多路增广的就是dinic算法

当然最坏情况的时间复杂度也是 ，但是实际应用的话能解决 级别的网络

当前弧优化

我们可以加一个小小的优化，把最坏时间复杂度从 优化成

为了优化，我们引入几个之前就该先引入的概念，但是因为这个对于前面的理解帮助不大，所以在这里才说

弧：其实就是一条路径
弧流量：这个弧上的流量，即弧上最小边的容量

为什么叫当前弧优化呢，我们回顾dinic的dfs，我们就相当于从源点疯狂灌水，把能灌过去的全灌的，所以之前灌过一次的地方，它的流量一定是被”榨干”的，下次再灌的时候直接跳过即可

但是这里要注意，当前弧是只针对一个分层图进行优化的，当dfs结束重新分层时，要重置 cur 数组

具体做法就是定义一个当前弧数组 cur ，在每次bfs时将 head copy一份到 cur 中，然后在dfs里每次记录下在哪条边上跳出循环，把编号赋给 cur ，每次遍历一个点时就从 cur 开始而不是 head

这样顶多遍历一遍每个点而不是每条边，成功把复杂度优化到

dinic算法效率已经很高了，除了luogu上那个预流推进的模板题目前没找到卡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;

#define ll long long
#define MAXN 105
#define MAXM 5005
#define inf LLONG_MAX

namespace chain_forward_star{
    struct edge{
        int to, next, flow;
    }side[MAXM*2];
    int head[MAXN], ccnt = 1;
    void insert(int from, int to, int flow)
    {
        side[++ccnt] = {to, head[from], flow}; head[from] = ccnt;
        side[++ccnt] = {from, head[to], 0}; head[to] = ccnt;
    }
}
using namespace chain_forward_star;

int n, m, s, t;
int dis[MAXN];

ll dinic();
bool bfs(int s, int t);
ll dfs(int x, ll flow);

int main()
{
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++)
    {
        int u, v, f;
        cin >> u >> v >> f;
        insert(u, v, f);
    }

    cout << dinic();
}

ll dinic()
{
    ll maxflow = 0, flow;
    while(bfs(s, t))
        maxflow += dfs(s, inf);
    return maxflow;
}
bool bfs(int s, int t)
{
    memset(dis, 0, sizeof(dis));
    queue<int> q; int x;
    q.push(s); dis[s] = 1;
    while(q.size())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and !dis[side[i].to])
            {
                dis[side[i].to] = dis[x]+1;
                q.push(side[i].to);
                if(side[i].to == t)
                    return true;
            }
        }
    }
    return false;
}
ll dfs(int x, ll flow)
{
    if(x == t) return flow;
    ll rest = flow;
    for(int i = head[x]; i; i = side[i].next)
    {
        if(side[i].flow and dis[side[i].to] == dis[x]+1)
        {
            int k = dfs(side[i].to, min(rest, (ll)side[i].flow));
            if(k == 0) dis[side[i].to] = -1;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest-=k)) break;
        }
    }
    return flow-rest;
}

例题: 板子 P2472

最小割

割的定义：在网络流中，设源点为 ，汇点为 ，所有点的总集为 ，将图中点分成两个集合 ， ，，且 ，称其为割

割的容量：所有两端的点不属于同一个集合的边的容量的总和，就是割掉的边的容量和

求最小割就是求最小的割的容量

这里有一条定理：任意一个割大于等于任意一个流，我们来证一下：

我不会那种非常严谨、语言非常规范的证明，所以我们回到开头那个比喻，首先，一个割肯定要把所有水流切断，否则 和 就是联通的，水流一定小于等于水管能承载的流量，而割的容量又等于水管的容量，所以流一定小于等于割

有了这个定理，我们就可以得到： 最小割等于最大流

最小割通常适用于选择有冲突时求出最小花费或最大取值一类的题

代码就不给了，就是最大流代码

最小割的题大多数是给定一些比较恶心的限制然后让你求出一个选择方案使得选择的价值最大，一般这种题用最大流很难建出来模型，这时我们就可以正难则反，我们假设先把所有的都选上，然后删去冲突的方案，删去最小的就相当于求最大的，最后建最小割模型就简单多了

例题：P4313 P2774 P2762

最小费用最大流

为了解决更多的问题，边上多加一个权值 cost ，代表单位流量的花费，然后我们不仅要求出最大流，还要求出最大流状态下的最小总费用

首先，我们知道，在一条增广路上，整条增广路的流量由路径上残量最小的边决定，整条增广路的流量都是 min(flow) ，所以这条增广路的费用就是 sum(dis)*min(flow) 。

因为最大流的流量唯一，但方法不一定唯一，所以我们可以贪心一手，每次先处理出来最短路，在最短路上找增广路，一直增广到图不连通，这样我们找到的最大流一定是费用最小的。

这里注意反向边的处理，因为我们反向边是用来反悔的，走了反向边就相当于回退原边的流量，原边的费用肯定也要回退 (rnm，退钱) ，所以反向边的费用应该是 -cost

因为反边的存在，我们需要能处理负边权的最短路算法，于是SPFA又在网络流里活了…，当然也有可能被卡，但是我目前没遇到，如果需要更快的最短路请出门左转百度带势dij

所以我们把最大流的bfs换成SPFA就可以得到最小费用最大流的算法了，这里注意dinic中的dfs要标记走过的点，不要在 cost=0 的边上转圈…

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

#define MAXN 5005
#define MAXM 50005
#define inf 2147483647

namespace chain_forward_star{
    struct edge{
        int to, next, flow, cost;
    }side[MAXM*2];
    int head[MAXN], ccnt = 1;
    void insert(int from, int to, int flow, int cost)
    {
        side[++ccnt] = {to, head[from], flow, cost}; head[from] = ccnt;
        side[++ccnt] = {from, head[to], 0, -cost}; head[to] = ccnt;
    }
}
using namespace chain_forward_star;

int n, m, s, t;
int dis[MAXN], cur[MAXN];
bool inque[MAXN], vis[MAXN];


pair<int,int> dinic();
bool spfa(int s, int t);
int dfs(int x, int flow);

signed main()
{
    cin >> n >> m; s = 1, t = n;
    for(int i = 1; i <= m; i++)
    {
        int u, v, f, c;
        cin >> u >> v >> f >> c;
        insert(u, v, f, c);
    }


    pair<int,int> ans = dinic();
    cout << ans.first << ' ' << ans.second;
}

pair<int,int> dinic()
{
    int maxflow = 0, mincost = 0;
    while(spfa(s, t))
    {
        int flow = dfs(s, inf);
        maxflow += flow;
        mincost += flow*dis[t];
    }
    return {maxflow, mincost};
}
bool spfa(int s, int t)
{
    memcpy(cur, head, sizeof(head));
    memset(dis, 0x7f, sizeof(dis));
    queue<int> q; int x;
    q.push(s), dis[s] = 0;
    while(q.size())
    {
        x = q.front(); q.pop();
        inque[x] = false;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and dis[side[i].to] > dis[x] + side[i].cost)
            {
                dis[side[i].to] = dis[x] + side[i].cost;
                if(!inque[side[i].to])
                {
                    q.push(side[i].to);
                    inque[side[i].to] = true;
                }
            }
        }
    }
    return dis[t] != 0x7f7f7f7f;
}
int dfs(int x, int flow)
{
    if(x == t) return flow;
    int rest = flow, i;
    vis[x] = true;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and !vis[side[i].to] and dis[side[i].to] == dis[x] + side[i].cost)
        {
            int k = dfs(side[i].to, min(rest, side[i].flow));
            if(!k) dis[side[i].to] = 0;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest-=k)) break;
        }
    }
    cur[x] = i;
    vis[x] = false;
    return flow-rest;
}

例题: 板子 P4012 P4015 UVA1411 UVA1658 P4066

二分图匹配

以网络流的特性来看，肯定能很容易地解决二分图匹配问题，因为限制流量就可以限制每个点的匹配数、被匹配数，多重匹配问题也随之解决

对于二分图带权匹配更简单了，直接权值取负数跑最小费用最大流，再对费用取反就可以直接解决二分图带权匹配问题

例题: P2756 P1231

网络流建模

网络流的题一般不直接考板子，因为网络流代码就是普及难度，重在如何把板子套进题里，把网络流的模型建出来，以下是几种常用的建模方式:

  1. 无脑建图法：题目怎么建就跟着怎么建，完全按着题目给的来，敲个板子就开始跑，这种题一般数据范围较大，建议使用高效算法

  2. 超级源点汇点法：最常用的方法，一般题目要么不给源点汇点，要么有很多源点汇点，这时我们可以通过建立超级源点和超级汇点连到题目给的源点上，从而减小建模难度
    例题：P2756

  3. 点转边：有的时候题目并不直接对边操作，而是对点操作，这时我们就要把操作点转变为操作边，我们可以把点拆开，拆成两个点和一条边(视题目而定)，这样我们删除这条边就相当于删除这个点，然后愉快的跑网络流就好了
    例题：P1345 P1251

  4. 拆点：其实点转边就是一种拆点，但是真正的拆点不见得只拆两个，也可以拆好几个，网络流的题一般就是经过一堆神仙操作之后把问题莫名其妙地转化成了最大流问题…

  5. 拆边法：有的时候一条边的限制很恶心，我们可以把一条边拆成多条部分边来分别解决问题
    例题：UVA1486

练习题：网络流24题

上下界网络流

无源汇上下界可行流

为了解决亿些更复杂的问题，光是有流量上限还不行，每个边的流量都有一个上界和下界，求是否存在一个流可以满足所有边的上下界和所有点流量平衡

首先这个下界很烦，有这个下界我们就很难套上面的板子，于是我们想办法把这个下界消掉

我们可以先满足所有边的下界，这样每条边就只剩下一个 r-l 的上界了，可以扔到普通网络流的板子里

但是这样又诞生了许多问题，首先满足下界之后势必会有一些点不满足流量平衡，一些点存了流量，一些点透支了流量，我们设每个点所存的流量为 val ，即流入量减去流出量

我们需要在满足上界的条件下，把存下的流量推送给透支的流量上，达到满足流量平衡

于是我们得想办法让一股流从多的点流到少的点，但我们又不能凭空造流，否则不满足流量平衡，于是我们需要建一个虚拟源点汇点，因为最大流中源点汇点可以不满足流量平衡

所以对于 val>0 的点，我们从 s 向它建一条流量为val的边，对于 val<0 的点，我们从它向 t 建一条流量为 -val 的边，然后跑最大流，这样我们所有存下的流量就可以流到透支的地方去了

设所有存下的流量为 sum ，即 ，如果跑出来的流量等于 sum 的话，证明可以平衡掉所有的流量，即存在可行流，如果小于 sum 的话证明没有可行流

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
103
104
105
106
#include<bits/stdc++.h>
using namespace std;

#define MAXN 205
#define MAXM 20200
#define inf 2147483647

namespace chain_forward_star{
    struct edge{
        int to, next, flow, r;
    }side[MAXM*2];
    int head[MAXN], ccnt = 1;
    void insert(int from, int to, int l, int r)
    {
        side[++ccnt] = {to, head[from], r-l, r}; head[from] = ccnt;
        side[++ccnt] = {from, head[to], 0, r}; head[to] = ccnt;
    }
}
using namespace chain_forward_star;

int n, m, s, t;
int val[MAXN], cur[MAXN], dis[MAXN];

int dinic();
bool bfs(int s, int t);
int dfs(int x, int flow);

signed main()
{
    cin >> n >> m;
    s = n+1, t = n+2;
    for(int i = 1; i <= m; i++)
    {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        insert(u, v, l, r);
        val[u] -= l, val[v] += l;
    }
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(val[i] > 0)
        {
            insert(s, i, 0, val[i]);
            sum += val[i];
        }
        else if(val[i] < 0)
            insert(i, t, 0, -val[i]);
    }
    if(dinic() < sum)
        cout << "NO";
    else
    {
        cout << "YES\n";
        for(int i = 2; i <= m*2; i += 2)
            cout << side[i].r-side[i].flow << '\n';
    }
}

int dinic()
{
    int maxflow = 0;
    while(bfs(s, t))
        maxflow += dfs(s, inf);
    return maxflow;
}
bool bfs(int s, int t)
{
    memcpy(cur, head, sizeof(head));
    memset(dis, 0, sizeof(dis));
    queue<int> q; int x;
    q.push(s); dis[s] = 1;
    while(q.size())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and !dis[side[i].to])
            {
                dis[side[i].to] = dis[x]+1;
                q.push(side[i].to);
                if(side[i].to == t)
                    return true;
            }
        }
    }
    return false;
}
int dfs(int x, int flow)
{
    if(x == t) return flow;
    int rest = flow, k, i;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and dis[side[i].to] == dis[x]+1)
        {
            k = dfs(side[i].to, min(rest, side[i].flow));
            if(k == 0) dis[side[i].to] = -1;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest-=k)) break;
        }
    }
    cur[x] = i;
    return flow-rest;
}

例题: 板子

有源汇上下界最大流

这个问题多了源汇，因为源汇是不需要满足流量平衡的，所以没法直接跑出可行流

以下部分将题目给的源汇设为 s1, t1 ，可行流中建立的虚拟源汇设为 s, t

这时候我们就可以从 t1->s1 建一条流量为 inf 的边，直接转化为无源汇问题，我们跑无源汇上下界可行流即可

但是直接跑的话可能没有达到最大流量，因为我们只满足了下界

但是我们已经满足下界了，就相当于没有了下界这个条件，这时再跑一次 s1->t1 的最大流，加到答案中，就是有源汇上下界最大流的答案了

因为跑出可行流之后已经满足了流量平衡，这时跑最大流除了 s1 和 t1 也是都满足流量平衡的，然后最大流会把能跑的流量全跑完，所以就可以求出答案来

这里要特别注意一定要删去之前建的 t1->s1 的边，否则就是一个死循环打到你脸上你也没法debug

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define MAXN 50010
#define MAXM 125010
#define inf LLONG_MAX

int n, m, s, t, s1, t1;
int val[MAXN], dis[MAXN];

namespace chain_forward_star{
    struct edge{
        int from, to, next;
        ll flow;
    }side[MAXM*2+MAXN*2];
    int head[MAXN], cur[MAXN], ccnt = 1;
    void insert(int from, int to, ll l, ll r)
    {
        side[++ccnt] = {from, to, head[from], r-l}; head[from] = ccnt;
        side[++ccnt] = {to, from, head[to], 0}; head[to] = ccnt;
    }
}
using namespace chain_forward_star;

ll dinic();
bool bfs(int s, int t);
ll dfs(int x, ll flow);

signed main()
{
    cin >> n >> m >> s1 >> t1;
    s = n+1, t = n+2;
    for(int i = 1; i <= m; i++)
    {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        insert(u, v, l, r);
        val[u] -= l, val[v] += l;
    }
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(val[i] > 0)
        {
            insert(s, i, 0, val[i]);
            sum += val[i];
        }
        else if(val[i] < 0)
            insert(i, t, 0, -val[i]);
    }
    insert(t1, s1, 0, inf);



    if(dinic() < sum)
        cout << "please go home to sleep";
    else
    {
        ll ans = side[ccnt].flow;
        side[ccnt].flow = side[ccnt^1].flow = 0;
        s = s1, t = t1;
        ans += dinic();
        cout << ans;
    }

}

ll dinic()
{
    ll maxflow = 0;
    while(bfs(s, t))
        maxflow += dfs(s, inf);
    return maxflow;
}
bool bfs(int s, int t)
{
    memset(dis, 0, sizeof(dis));
    memcpy(cur, head, sizeof(head));
    queue<int> q; int x;
    q.push(s); dis[s] = 1;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and !dis[side[i].to])
            {
                dis[side[i].to] = dis[x] + 1;
                q.push(side[i].to);
                if(side[i].to == t)
                    return true;
            }
        }
    }
    return false;
}
ll dfs(int x, ll flow)
{
    if(x == t) return flow;
    ll rest = flow; int k, i;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and dis[side[i].to] == dis[x]+1)
        {
            k = dfs(side[i].to, min(rest, side[i].flow));
            if(k == 0) dis[side[i].to] = 0;
            side[i].flow -= k;
            side[i^1].flow += k;
            rest -= k;
            if(rest == 0) break;
        }
    }
    cur[x] = i;
    return flow-rest;
}

例题: 板子 P5192

有源汇上下界最小流

其实跟上面差不多，最小流不就是尽量让流变小吗，我们可以先跑出可行流，然后从 t1->s1 跑一边最大流(感性理解)，减去跑出的流量，就是最小流的答案

瞎扯两句

关于网络流的时间复杂度问题，网络流问题一般不能不需要计算复杂度，毕竟这玩意就是玄学复杂度，除非你用预流推进，不然复杂度基本是没法确定的，但该能过的还是能过XD

这个东西代码只是普及难度，但是建模吧…这个是真的ex

一些资料

网络流建模