首页 > 其他分享 >网络流学习笔记

网络流学习笔记

时间：2023-07-10 18:48:16浏览次数：45  
标签：idx int flow 网络 笔记 ne 学习 dep 流量

网络流

基本概念

（from OIwiki）

网络：有向图 \(G = (V, E)\)，其中每条边有一个流量 \(c\)，当 \((u, v) \notin E\) 时，\(c_{(u, v)} = 0\)。其中有两个特殊的点：源点 \(s \in V\)，\(t \in V\)。

流：定义函数 \(f(u, v)\)，满足下列条件：

  1. 容量限制：\(f(u, v) \le c(u, v)\)。
  2. 斜对称性：\(f(u, v) = -f(v, u)\)。
  3. 流守恒性：\(\forall x\in V-\{ s, t\}, \sum_{(s,x)\in E} f(u, x)=\sum _{(x,v)\in E} f(x,v)\)

最大流

定义：有一张网络，要求从 \(s\) 到 \(t\) 的最大流量。

剩余容量：对于边 \((u, v)\)，剩余容量为 \(c(u, v) - f(u, v)\)。

残量网络：将 \(G\) 中所有点和所有剩余容量大于 \(0\) 的边构成的子图称为残量网络。

增广路：从源点到汇点的路径。

可以证明，当残量网络中没有增广路存在时，网络达到最大流。

Dinic 算法

分层图：\(G_L = (V, E_L),E_L=\{(u, v)|d_v=d_u+1\}\) 的图。

阻塞流：在分层图 \(G_L\) 中找到的最大的增广流，使得仅在 \(G_L\) 上无法找到更大的增广流。

算法流程：先在残量网络中 bfs 一遍，构造出分层图。再在分层图上 dfs 出阻塞流。循环这个过程直至残量网络无法找到增广路。

当前弧优化：在 dfs 的过程中，及时将已经扩展完的边或者是无法扩展的边从图中删去。

代码实现：

#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
const ll INF = 1e17;
int h[N], e[N], ne[N], w[N], idx;
int now[N], d[N];
int n, m;
ll flow, maxflow;

inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

queue<int> q;
bool bfs()
{
    memset(d, 0, sizeof d);
    while(q.size()) q.pop();
    d[1] = 1;
    now[1] = h[1];
    q.push(1);
    while(q.size())
    {
        int u = q.front();
        q.pop();

        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(!d[v] && w[i])
            {
                d[v] = d[u] + 1;
                now[v] = h[v];
                q.push(v);
                if(v == n) return true;
            }
        }
    }
    return false;
}

ll dinic(int x, ll flow)
{
    if(x == n) return flow;
    ll rest = flow, k;
    int i;
    for(i = now[x]; i != -1; i = ne[i])
    {
        now[x] = i; //  当前弧优化
        int v = e[i];
        if(d[v] == d[x] + 1 && w[i])
        {
            k = dinic(v, min((ll)w[i], rest));
            if(!k) d[v] = 0;
            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

// in main
while(bfs())
    while(flow = dinic(1, INF))
        maxflow += flow;
    
cout << maxflow << endl;

HLPP 算法 预流推进

上面的 Dinic 算法时间复杂度为 \(O(n^2m)\)，一般情况下表现良好。但是当图的规模增加时，则需要复杂度更小的算法。HLPP 的算法为 \(O(n^2\sqrt m)\)。

在 HLPP 算法中，每个节点引入了高度的概念，为汇点到该点的距离。同时每个点上存储了一个溢出值，当向下推流时，先将流量储存在该点中，以便后面的搜索。

算法流程：

  1. BFS 出每个节点的高度。
  2. 从源点开始搜索，将与 s 相连的边跑到满流，多出的流使得这些点溢出，放入优先队列。
  3. 按从高到低更新每个节点，把溢出节点放入优先队列。
  4. 如果该节点无法找到合法路径且还有溢出流量，把它的高度提升到它邻居的最低值加一。
  5. 重复 3、4，直至没有溢出节点。

GAP 优化：当高度出现断层时，该高度以上的节点都无法进行流量的更新，则让这些点高度全部变为 \(n+1\)，以便推送回 \(s\)。

代码实现：

#define LOCAL
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, INF = 2147483647;
int h[N], e[N], ne[N], w[N], idx;
int dep[N], flow[N], gap[N];
int n, m, s, t;

inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool is_in[N], is[N];
bool bfs()
{
    for(int i = 1; i <= n; i ++ ) dep[i] = INF;
    dep[t] = 0;
    queue<int> q;
    q.push(t);
    is[t] = true;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        is[u] = false;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(w[i] || dep[v] <= dep[u] + 1) continue;
            dep[v] = dep[u] + 1;
            if(!is[v])
            {
                q.push(v);
                is[v] = true;
            }
        }
    }
    return dep[s] == INF;
}

struct cmp
{
    bool operator () (int a, int b) const
    {
        return dep[a] < dep[b];
    }
};

priority_queue<int, vector<int>, cmp> q;
inline void push(int u)
{
    int nowflow = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(!w[i] || dep[u] != dep[v] + 1) continue;
        nowflow = min(flow[u], w[i]);
        w[i] -= nowflow;
        w[i ^ 1] += nowflow;
        flow[u] -= nowflow;
        flow[v] += nowflow;
        if(!is_in[v] && v != t && v != s)
        {
            q.push(v);
            is_in[v] = true;
        }
        if(!flow[u]) break;
    }
}

inline void relabel(int u)
{
    dep[u] = INF;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(!w[i]) continue;
        int v = e[i];
        dep[u] = min(dep[u], dep[v] + 1);
    }
}

int maxflow()
{
    if(bfs()) return 0;
    dep[s] = n;
    
    for(int i = 1; i <= n; i ++ )
        if(dep[i] < INF)
            gap[dep[i]] ++;
    
    for(int i = h[s]; i != -1; i = ne[i])
    {
        int v = e[i];
        int nowflow = w[i];
        if(nowflow)
        {
            flow[s] -= nowflow;
            flow[v] += nowflow;
            w[i] -= nowflow;
            w[i ^ 1] += nowflow;
            if(v != t && v != s && !is_in[v])
            {
                q.push(v);
                is_in[v] = true;
            }
        }
    }

    while(q.size())
    {
        int u = q.top();
        q.pop();
        is_in[u] = false;
        push(u);
        if(flow[u])
        {
            gap[dep[u]] --;
            if(!gap[dep[u]])
            {
                for(int i = 1; i <= n; i ++ )
                    if(i != s && i != t && dep[i] > dep[u] && dep[i] < n + 1)
                        dep[i] = n + 1;
            }
            relabel(u);
            gap[dep[u]] ++;
            q.push(u);
            is_in[u] = true;
        }
    }
    return flow[t];
}

补充：二分图

最大匹配：在二分图中选出一些边，使得这些边没有公共顶点，且边的数量最大。

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

最大独立集：选最多的点，满足两两点之间没有边直接相连。

最小路径覆盖：DAG 中用最少的不相交的路径将所有点连接。

König 定理

在二分图中，最大匹配=最小点覆盖=总点数-最大独立集=总点数-最小路径覆盖

最小割

定义

割：点的划分方式，将点集划分为 \(S\) 和 \(T = V - S\) 两个集合，使得 \(s \in S\) 且 \(t \in T\)。

割的容量：所有从 \(S\) 到 \(T\) 的边的容量之和，记为 \(c(S, T)\) 或 \(c(s, t)\)

最大流最小割定理

\[f(s, t)_{max} = c(s, t)_min \]

应用

普通网络流

边的流量可以用来建模成对某个条件使用的限制次数，建出图跑最大流。

二分图最大匹配

对于一张二分图，我们可以建一个超级源点 \(s\) 和超级汇点 \(t\)，\(s\) 向左部点连流量为 \(1\) 的边，右部点向 \(t\) 连流量为 \(1\) 的边，左部点和右部点直接连流量为 \(1\) 的边。从 \(s\) 开始跑最大流即可。

二分图多重匹配

对于每一个点，它的最大匹配数对应的就是超级源点/汇点和它之间边的最大流量大小。建图跑最大流即可。

例题

P2065 [TJOI2011] 卡片

本题组数就可看成匹配的对数，两种颜色的卡牌可以看成左部点和右部点，于是建图跑网络流。

发现如果暴力建图是 \(O(Tn^2\log n) \approx 67474250\) 的，考虑优化。

我们可以将每个点连到它的质因子上，质因子就可以充当一个桥梁，连接具有公因子的点。然后就可以愉快跑最大流了 φ(゜▽゜*)♪

但是这时我们发现好像直接分解质因数的复杂度是 \(O(Tn\sqrt MAXN) \approx 316227766\)，甚至比之前还慢，我们再考虑考虑怎么优化。

我们可以预处理出所有的质数，然后分解的时候直接用质数去筛即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int d[N], now[N];
int primes[N * 10], cnt;
map<int, int> mp;
bool st[N * 10];
int n, m, s, t;
int flow, maxflow;

inline void init(int n)
{
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            primes[++ cnt] = i;
            mp[i] = cnt;
        }
        for(int j = 1; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

inline void build(int id, int x, int op)
{
    for(int i = 1; primes[i] <= x / primes[i]; i ++ )
    {
        if(x % primes[i] == 0)
        {
            if(op == 0) add(id, i + m + n + 1, 1);
            else add(i + m + n + 1, id, 1);
            while(x % primes[i] == 0) x /= primes[i]; 
        }
    }
    if(x > 1) 
    {
        if(op == 0) add(id, mp[x] + m + n + 1, 1);
        else add(mp[x] + n + m + 1, id, 1);
    }
}

int main()
{
    int T = read();
    init(10000000);
    while(T -- )
    {
        init();
        n = read(), m = read();
        for(int i = 1; i <= n; i ++ )
        {
            int x = read();
            build(i, x, 0);
        }

        for(int i = 1; i <= m; i ++ )
        {
            int x = read();
            build(i + n, x, 1);
        }

        s = 0, t = N - 2;
        for(int i = 1; i <= n; i ++ ) add(s, i, 1);
        for(int i = 1; i <= m; i ++ ) add(i + n, t, 1);

        while(bfs())
            while(flow = dinic(s, INF))
                maxflow += flow;
        
        cout << maxflow << endl;
        maxflow = 0;
    }
    
    return 0;
}

P2763 试题库问题

本题是一个比较裸的二分图多重匹配，每个试题只能被选一次，每种类别要选 \(k_i\) 次。我们就可以把试题看成右部点，向 \(T\) 连流量为 \(1\) 的边，把类型看成左部点，从 \(S\) 向其连流量为 \(k_i\) 的边。

过水我就不放代码了。

P2472 [SCOI2007] 蜥蜴

本题有柱子跳跃次数的限制，我们可以把一根柱子拆成两个点，一个入点一个出点，入点向出点连流量为该柱子所能跳跃的次数的边。从源点向蜥蜴在的位置连流量为 \(1\) 的边，跑最大流即可。

注意题中的距离为欧几里得距离。

部分代码：

for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
    {
        in[get(i, j)] = get(i, j);
        out[get(i, j)] = get2(i, j);
        if(mp[i][j] != '0') add(get(i, j), out[get(i, j)], mp[i][j] - '0');
    }

for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
        if(mp[i][j] != '0')
        {
            k ++;
            x[k] = i, y[k] = j;
        }

for(int i = 1; i <= k; i ++ )
    for(int j = 1; j <= k; j ++ )
    {
        if(i == j) continue;
        if(dist(x[i], y[i], x[j], y[j]) <= maxd * maxd)
            add(out[get(x[i], y[i])], in[get(x[j], y[j])], INF);
    }

for(int i = 1; i <= k; i ++ )
{
    int x1 = x[i], y1 = y[i];
    if(x1 + maxd > r || x1 - maxd < 1 || y1 + maxd > c || y1 - maxd < 1) 
        add(out[get(x[i], y[i])], t, INF);
}

for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
        if(frog[i][j] == 'L')
        {
            add(s, in[get(i, j)], 1);
            num ++;
        }

while(bfs())
    while(flow = dinic(s, INF))
        maxflow += flow;

cout << num - maxflow << endl;

未完待续

标签：idx,int,flow,网络,笔记,ne,学习,dep,流量
From： https://www.cnblogs.com/crimsonawa/p/17541992.html

相关文章

  • PAM学习笔记
    PAM回文树（又称回文自动机\(\texttt{PAM}\)），是一种可以高效解决大部分回文串问题的算法，在大部分情况下可以替代马拉车（当然模板题好像都替代不了），是一种不错的算法。结构trie类似于其他的自动机（\(\texttt{AC}\)自动机、\(\texttt{SAM}\)），\(\texttt{PAM}\)也有一颗\(\texttt{tr......
  • ChatGPT 英语学习 prompt
    YouareanativeEnglishspeaker,andyouareteachingahighschoolstudentaboutEnglish.YouwillbegivenEnglishwordorphrases,pleaseexplaintheirmeaninginaeasy-to-understandway,including:thecharacteristicorpropertyofacertainword,......
  • 斜率优化dp学习笔记
    前置知识单调队列优化dp，计算几何基础知识，小学数学。斜率优化在dp中，我们常常能遇到一类转移方程，其中含有\(i\)相关的项与\(j\)相关的项的乘积，形如这种形式：\[f_i=\max_{j<i}\{f_j+a_ib_j\}\]我们常见的单调队列优化只能优化只含\(j\)项的方程，对于这种方程无能为力。......
  • cdq分治学习笔记
    做着做着cdq分治的题发现自己太菜了写不出来题XD，所以来写写学习笔记。CDQ分治CDQ分治一般有两个用途：解决偏序问题、将动态问题转化为静态问题。偏序问题我们先来介绍第一个问题：偏序问题。普通的二维偏序就类似于逆序对，每个元素有两个属性\(a_i,b_i\)，我们需要统计\(a_......
  • java类和对象学习总结
    当一个引用赋值为null的时候,就代表这个引用不指向任何的对象引用不能指向引用,只能说引用指向了另一个引用的对象.一个引用不能指向多个对象this引用的学习:代表的是当前对象的引用,每一个成员方法的第一个参数默认是thisthis.year this.month   加上this代表给当前的对象......
  • 3学习记录
    pycharm1.”enter+shift“----一键格式化代码2.”#“”ctrl+/“----单行注释3.“Ctrl+d”------直接复制一行代码4.“Ctrl+y”-----删除一行代码5.tab----代码向后缩进6.Shift+Tab----代码向前取消缩进7.CTRL+SHIFT+/----块注释......
  • web安全学习日志---xss漏洞（跨站脚本攻击）
    1.反射性xss（reflacted） 仅执行一次，非持久型。主要存在于攻击者将恶意脚本附加到url的参数中，发送给受害者，服务端未经严格过滤处理而输出在用户浏览器中，导致浏览器执行代码数据。利用场景：直接插入JS代码，修改url参数  攻<script>alert('hack')</script>防$name=str_replac......
  • 整体二分学习笔记
    整体二分引入对于一堆询问，如果每个单独的询问都可以二分解决的话，时间复杂度为\(O(NM\logN)\)，但实际上每次二分都会有一些残留信息被我们扔掉，如果我们将所有询问一起二分，就可以最大时间的减小复杂度。讲解经典例题：区间第k大给定一个序列a和一个整数S，有2种操作：1.将a......
  • 《ReAct: SYNERGIZING REASONING AND ACTING IN LANGUAGE MODELS》论文学习
    一、论文主要思想本文首先认为，到目前为止，LLM在语言理解方面令人印象深刻，它们已被用来生成CoT（思想链）来解决一些问题，它们也被用于执行和计划生成。尽管这两者是分开研究的，但本文旨在以交错的方式将推理和行动结合起来，以提高LLM的表现。这个想法背后的原因是，如果你考虑一下作为......
  • redis学习十七：redis事务
    概念：可以一次执行多个命令，本质是一组命令的集合。一个事务中的所有命令都会序列化，按顺序地串行化执行而不会被其他命令插入，不许加塞。1.单独的隔离操作redis的事务仅仅是保证事务里的操作会被连续独占的执行，redis命令执行是单线程架构，在执行完事务内所有指令前是不可能再去......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99