网络流

基础知识

网上博客有很多，这里就没必要再赘述了。

贴一份 \(yxc\) 的笔记：1. 基本概念     1.1 流网络，不考虑反向边     1.2 可行流，不考虑反向边         1.2.1 两个条件：容量限制、流量守恒         1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量         1.2.3 最大流是指最大可行流     1.3 残留网络，考虑反向边，残留网络的可行流f'   原图的可行流f = 原题的另一个可行流         (1) |f'   f| = |f'|   |f|         (2) |f'| 可能是负数     1.4 增广路径     1.5 割         1.5.1 割的定义         1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。         1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T)         1.5.4 对于任意可行流f，任意割[S, T]，|f| = f(S, T)         1.5.5 对于任意可行流f，任意割[S, T]，|f| <= c(S, T)         1.5.6 最大流最小割定理             (1) 可以流f是最大流             (2) 可行流f的残留网络中不存在增广路             (3) 存在某个割[S, T]，|f| = c(S, T)     1.6. 算法         1.6.1 EK O(nm^2)         1.6.2 Dinic O(n^2m)     1.7 应用         1.7.1 二分图             (1) 二分图匹配             (2) 二分图多重匹配         1.7.2 上下界网络流             (1) 无源汇上下界可行流             (2) 有源汇上下界最大流             (3) 有源汇上下界最小流         1.7.3 多源汇最大流

最大流

个人认为比较重要的几个点就是：

建的是原图的残留网络

每次增大就相当于减小残留网络中的容量。

分层思想

保证流的顺序。

当前弧优化

别的我不知道，我只知道如果没有它你会死翘翘。

详细分析也不讲啦，这里推荐一篇证明博客

费用流

费用流是基于网络流，只是多了一个费用的条件限制。

算法核心应该就是利用 \(spfa\) 可以处理负权的功能进行最短路。

注意点：

流量处理时要注意一定是“照顾弱小”。但是初始值为 \(inf\)。

利用链式前向星的特性记录路径就很妙。

建图总结

其实大家都可以发现，网络流难点在于建图，只要把图建对，走遍天下都不怕。

然而建图都是有规律可循的，所以总结一发。

一、常规建图（又名直接来）

现在一般都不会出现直接建图的情况了。。。

一共有 \(n\) 个飞行员，其中有 \(m\) 个外籍飞行员和 \((n - m)\) 个英国飞行员，外籍飞行员从 \(1\) 到 \(m\) 编号，英国飞行员从 \(m 1\) 到 \(n\) 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

\(Solution\):

直接将外籍飞行员和可以配合的英国飞行员连边， 每个外籍向源点，英籍向汇点连容量为1的边，以控制每人只能配对一次。

建图：for(rt i = 1; i <= m; i   ) add(s,i,1); for(rt i = m   1; i <= n; i   ) add(i,t,1); read(a), read(b); while(~a && ~b) { add(a,b,1); read(a),read(b); }

舞会

某学校要召开一个舞会。已知学校所有 \(n\) 名学生中，有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上，要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。

\(Solution\):

反向思考，题目要求最多邀请人数，其实就是求最小不邀请人数，那么就转化成了求所有相互跳过舞的人中的最小割。

注意，因为题目没有给定男女生的具体情况，所以要先做染色处理，确定男女生，不同性别连向不同端点，跳过舞的一对就直接连边即可。

二、拆点（网络流一大热点）

就不用介绍了吧。

主要是用来控制每个点的使用次数的。

FJ的奶牛们只吃各自喜欢的一些特定的食物和饮料，除此之外的其他食物和饮料一概不吃。某天FJ为奶牛们精心准备了一顿美妙的饭食，但在之前忘记检查奶牛们的菜单，这样显然是不能不能满足所有奶牛的要求。但是FJ又不愿意为此重新来做，所以他还是想让尽可能多的牛吃到他们喜欢的食品和饮料。FJ提供了F （编号为1、2、…、F）种食品并准备了D （编号为1、2、…、D）种饮料， 他的N头牛（编号为1、2、…、N）都已决定了是否愿意吃某种食物和喝某种饮料。FJ想给每一头牛一种食品和一种饮料，使得尽可能多的牛得到喜欢的食物和饮料。每一种食物和饮料只能由一头牛来用。例如如果食物2被一头牛吃掉了，没有别的牛能吃到食物2。

\(Solution\):

传统思路，将食物、牛、饮料按顺序建成网络流，但是因为控制了数量，所以将奶牛割成两个点，前一个点连源点，后一个点连汇点，两个点之间连容量为1的边，就能保证每头牛只消耗一份食物和饮料。

代码戳这里

咕

三、分点（自定义）

其实我也不知道这个东东叫啥。

特点：利用题目给定的连边条件，将不同情况的点连向不同端点（感性理解一下）。

王者之剑

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

\(Solution\):

稍微观察就会发现，每个格点与他周围的四个格点的坐标和的奇偶性不同，说明相同奇偶性的格点不会相互排斥，也就是可以同时选。所以将不同奇偶性连向不同端点就好了。

如果坐标和为偶数（因为偶数与汇点相连），从当前点向周围四个点连边，边权为正无穷，意为连接的两个点不能同时选择。

代码戳这里

wyc的奇妙女友

wyc想出一道二分图（最大流），于是他找了女友们

单身多年的wyc终于找到了女朋友，而且一次性找到了\(inf\)个，wyc很喜欢她们里的所有人，但是害怕她们之间互相争斗导致自己后宫着火，wyc又十分喜欢挑战人类极限，想让一片街区有最多的女友可以让他肆意妄为，为了满足他的欲望，他找到了你来请你帮帮他。街区中的一个位置可以看做一个点。由于看上了wyc，wyc的女友们视野变得十分奇怪，她们只能看到目字型的位置，例如：如果她在点（5,5）上，她可以看到（6,8），（8,6）....（共八个）的点，如果wyc的一个女友看到了他的其他女友，那么她就会意识到wyc不仅有一个女友，wyc就会遭到迫害。现在wyc的女友们都在逛gai，已知街区大小为\(n*m\)（棋盘），其中有\(k\)个点没有wyc的女友，请问这条街区上最多可以有多少wyc的女友。

\(Solution\):

做题思维不能太固化，我拿到题就直接用坐标和建边，但是肯定是错的。观察图片，我们发现人所在的位置与她所能看见的位置的横、纵坐标的奇偶性各不相同，所以利用横或纵坐标来建边即可。

四、位置建边

其实就是将二维图转化成一维建图。

来源：https://www.icode9.com/content-4-823551.html