How to build a map?

by Ciaxin

大体概括 网络流和线性规划24题 中23道的模型与建图思路，以下所有的题目的思路均会向图论方向靠近。

# 飞行员配对方案问题

[link] 每一架飞机需要有一名英国飞行员和一名外籍飞行员。即，英国飞行员 \(v\) 与外籍飞行员 \(u\) 进行匹配，算出其最大匹配，所以此题模型为二分图的最大匹配。

对于二分图最大匹配而言，可由匈牙利算法 或 最大流模型 解决。

在一个流网络中，由点 \(u\) 向点 \(v\) 的一条边 \((u,v)\) 且 \(f(u,v)=1\) 可以理解为一个匹配。

很显然由一名外籍飞行员 \(u\) 所连向的边 \((u,v)\) 有多条，而最后的匹配仅会最多有一条，那就要保证从点 \(u\) 流出的流量为 \(1\)，才能保证最终只会连向一个点 \(v\)，那么建立源点 \(s\)，使得 \(s\) 到所有的点 \(u\) 的流量 \(f(s,u) = 1\)。

建立一条由点 \(v\) 流向汇点 \(t\) 的边，使完成的匹配流向汇点 \(t\)。

\[S\xrightarrow{\ \ 1\ \ }u_i\xrightarrow{\ \ 1\ \ }v_i\xrightarrow{\ \ 1\ \ }T \]

其最大流为二分图的最大匹配，而流过的流量为 \(0\) 的边，就是其匹配。

# 太空飞行计划问题

[link]对于每个实验 \(E_i\)，都会需要一定数量的仪器 \(I_k\)，需要选出 \(d\) 个实验使其净收益最大化。此题模型为最大权闭合子图。

但是我们不妨逆向思考，对于所有的实验 \(E\)，去掉 \(w\) 个实验使其净收益最大化，从而转化为 最小割模型。割掉的边即为去掉的某些实验。

同样建立一张流网络，实验 \(u\) 与仪器 \(v\) 间存在边 \(f(u,v) = +\infty\) 。（从而保证了被割去的边不会是该边）

由于进行每个实验将会获得为 \(p\) 的价值，所以用源点 \(S\) 连向点 \(u\) 流量为 \(p\) 的边。

将仪器点 \(v\) 连向汇点 \(T\)，使流量为 \(c\) 的边

这样由源点 \(S\) 到汇点 \(T\) 的增广路中存在 \(2\) 种情况：

\(最终流量 = 赞助费用\)，那么表示流量最终被源点 \(S\) 到点 \(u\) 的边 \(e_i\) 限制，割边即为 \(e_i\)，说明该实验的仪器费大于赞助费，不能使净收益最大化。
\(最终流量 \not= 赞助费用\)，那么表示限制的是花费仪器的边 \(e_j\)，割边即为 \(e_j\)，说明进行该实验存在收益。

若对于情况 \(1\)，用赞助费减去了流量，也就代表了没有进行这次实验；对于情况 \(2\)，赞助费减去流量为购买完仪器剩下的，即净收益。

因为经过计算后的割边流量为 \(0\)，而源点 \(S\)，连接着所有的实验 \(u\)，所以那些与源点联通的实验就是可执行的实验啦。

反边：当我们发现存在一个仪器由两个实验才能完全购买时，可能存在其中一个实验用尽了赞助费，此时好像不与源点 \(S\) 联通，但存在反边可以由上述仪器连到该实验，使其联通。

可以理解为这条反边将第两个实验的赞助费部分给予了第一个实验。

# 最小路径覆盖问题

[link]最小路径覆盖，在一个有向无环图（DAG）中，选取最少的路径，使每一个点仅存在与一条路径中。特别的，长度可以为 \(0\)。（可以理解为单点）

对于一个简单路 \(P\) 且 \((a,b)\in P\)，如果它要再覆盖一个点 \(c\)（存在点可以被覆盖），那么此时的路径覆盖数将会减一，点 \(b\) 也就连向了点 \(c\)，好像是多了一条匹配（别问我为啥蒟蒻也不知道），但由于点 \(a\) 也连向点 \(b\) 连了一条边，但由于两个点 \(b\) 的含义不太一样（一个是流入的，一个是流出的），这里有个非常套路的套路——拆点！！（把每个点 \(x\) 拆作点 \(x_1\) 与点 \(x_2\)）那这样就形成了两条由点 \(a_2\) 到点 \(b_1\)（作为流入），由点 \(b_2\)（作为流出）到点 \(c_1\) 的两条边，也就真真正正的形成了两条匹配。

由于在图中减小了一条路径覆盖，就相当于增加了一条拆点后的匹配，那么可以微微地解释了：

\[\Large{最小路径覆盖=节点数-新图的最大匹配数（拆点）} \]

那么我们把这个问题转换为了二分图最大匹配问题，从而可以用最大流模型求解。

注意：一个点 \(a\) 不可能存在点 \(a_1\) 向点 \(a_2\) 进行连边。因为不管是点 \(x_1\) 还是点 \(x_2\) 都只会形成最多一条匹配，所以其流量也为 \(1\)。

# 魔术球问题

[link]对于柱子来讲，所有的柱子将要把所有的球放入，且每个球只能存在其中一个柱子上，就像是我们要找到一个满足规则 \(2\) 的图，使得可以被所有的 \(k\) 个柱子覆盖，此题为最小路径覆盖问题。

“每次只能在某根柱子的最上面放球“，就像是原来最上面的球 \(b\) 与新球 \(c\) 产生了接触，原来的球又与下面的球 \(a\) 存在接触，就如 \(b\) 的下表面与 \(a\) 的上表面存在匹配，同 \(b\) 的上表面与 \(c\) 的下表面存在匹配。那么考虑拆点（把每个点 \(x\) 拆作点 \(x_1\) 与点 \(x_2\)）

由 \(最小路径覆盖=节点数-新图的最大匹配数（拆点）\)可知，这个问题就变成求二分图的最大匹配，从而可以用最大流模型求解。

虽然这个题目与求最小路径覆盖数恰恰相反，但我们也可以选择枚举每个可行图（每次加入新的边），来判断是否满足给出的最小路径覆盖数即可。

# 圆桌问题

[link]题意为需要满足一个类似，由点 \(u_i\) 连向 \(r_i\) 个点 \(v_j\)，每个点 \(v_j\)，仅存在 \(c_j\) 个入边的图。

如果当 \(r_i\) 与 \(c_i\) 均为 \(1\) 的时候，这个图很明显的是一张二分图的最大匹配，当对 \(r_i\) 与 \(c_i\) 不存在限制时，这就是一个二分图多重匹配问题。

由于每个单位的代表可向所有的餐桌进行挑选，并且两个代表不能做一个餐桌，所有这每个单位 \(u\) 要向所有的餐桌 \(v\) 连接一条流量为 \(1\) 的边。
因为每个单位的代表仅有 \(r_i\) 个，所以要限制从点 \(u\) 流出的流量为 \(r_i\)，由此建立源点 \(S\) 连向点 \(u\) 流量为 \(r_i\) 的边，从而限制了总的流量。‘
由于每个餐桌 \(v\) 将会被匹配多次，但由于餐桌的座位数量的限制，其最多为 \(c_i\) 个，所以最终到达 \(v\) 的流量最多为 \(c_i\)，这时利用汇点的作用，由点 \(v\) 连向汇点 \(T\) 一条流量为 \(c_i\) 的边从而限制了其数量。

由于点 \(u\) 向点 \(v\) 的流量为 \(1\)，所以最终如果该流量为 \(0\)，意味着该单位 \(u\) 有代表到了餐桌 \(v\)，从而得到方案。

# 最长不下降子序列问题

[link]该题需要进行三种不同的询问。

1、计算最长不下降子序列的长度 \(s\)

使用动态规划解决该问题，设计状态 \(f(i)\) 为以 \(i\) 结尾的最长子序列的长度，其当前状态可由前 \(i-1\) 个状态转移而来，即

\[f(i) = \max \begin{cases} \ \ \ \ \ 1\\ f(j) +1\ \ \ \ (a_i\ge a_j,i> j) \end{cases} \]

2、有多少个长度为 \(s\) 的不重复不下降子序列

由于每个点只能被选中一次，但并不每一个点都将会被选择一次，所以并不满足最小点覆盖的模型，但是此问题模型为最多不相交路径。

在DP的过程中，可以发现 \(i\) 的状态是由一个满足的 \(j\) 转移过来的，就像是由 \(j\) 连向了 \(i\) 的一条边。

序列中的每个点 \(i\) 均可作为这个不下降序列的开端，而仅仅是 \(\text{LIS}=s\) 的点 \(j\) 可以作为这个序列的结尾。

由此可以由源点 \(S\) 到每个点 \(i\)，连接一条流量为 \(1\) 的边，由满足的点 \(j\) 连向汇点 \(T\)，连接一条流量为 \(1\) 的边，从而可以算出该长度序列的数量。

限制条件：点只能被选中一次。这个问题可以用拆点的方法将其两个点中间连接一条流量为 \(1\) 的边，得到其解决方法。

3、有多少个不同的长度为 \(s\) 的不下降子序列。

限制条件：除 \(x_1,x_n\) 的点只能被选中一次。

因为限制点的方法是拆点，那么关于 \(x_1\) 与 \(x_n\) 的拆点的边的流量可以设置为 \(+\infty\)，意味不受选择次数的限制。

# 试题库问题

[link]对于 \(m\) 道题的每一个类型 \(i\) 需要 \(k\) 个试题 \(j\)，换句话说，就是点 \(i\) 要和 \(k\) 个 \(j\) 进行匹配，从而得到了该问题的模型 二分图多重匹配问题。

（与 [圆桌问题](# # 圆桌问题) 相似）可以转换为最大流求解。

对于每个类型 \(i\)，可以与所有类型为 \(i\) 的试题连接一条流量为 \(1\) 的边，作为可以选择的情况（匹配）。

每个类型的题有数量为 \(k\) 的限制，所以由源点 \(S\)，连向每个类型 \(i\) 流量为 \(k_i\) 的边。

又由每个试题 \(j\) 最多会被选择一次，所以连向汇点 \(T\) 处一条流量为 \(1\) 的边。

输出：同样的，匹配后的边即为流量变为 \(0\) 的边，输出即可。

# 方格取数问题

[link]在所有的数中，选取部分数（限制）的总和最大。

由于选取的数之间不存在什么联系，而仅有在四个方向的数才会有所制约，可以将理解为边。

一定不存在制约关系的一定是那些奇偶性相同的点，从此可以将其看做一个二分图，其此题为二分图点权最大独立集。

首先我们不先去想选中那些数，而是去考虑将所有的数选中，再去删掉某些数。最终的答案就是所有的数的和减去被删掉的数。

在众多模型中，可能会想到 最小割问题。（割：删掉的某些数）

由于最小割是边，所以考虑拆点。

但是由于转换成了网络流，存在源点与汇点，所以这个点权可以直接放在其之间（即，边权）。

而流过这些边就意味着选了这个点。若割为该边，即要删掉这个点。¹

因为对点 \(x_{i,j}\) 存在影响的是四个方向上的数，其中有边相连，但是这个边又不满足上述边 ¹的性质，所以将其流量设置为 \(+\infty\) 。

# 餐巾计划问题

[link]该问题模型是线性规划网络优化。由于该题很明显存在费用，能参考想到用费用流求出。

初读该题目，我会想到的一种做法是：

将每一天拆作早上与晚上两部分，由早上向晚上连接一条流量为 \(r_i\) ，花费为 \(0\) 的边。

将源点看做购买处，早上可由此购买 \(+\infty\) 条餐巾，费用为 \(p\)。

对于快洗与慢洗，分别由第 \(i\) 天的晚上到 \(i+m\) 和 \(i + n\) 的早上，流量为 \(+\infty\) ，花费为 \(f,s\)。

第 \(i\) 天晚上，也可以连向第 \(i+1\) 天的晚上。

最后由汇点收集。

当然，这之中存在一些问题。【详细参考】

这里提供另一个建图的方法，

在这一天的干净餐巾来源，有三处：购买得到，慢洗得到，快洗得到。这一天脏的餐巾有三个去处：送去快洗，送去慢洗，扔给下一天处理。

因为这一天需要 \(r_i\) 个干净餐巾，但是到这一天的干净餐巾可能大于 \(r_i\) 个，所以我们让每天恰好只对 \(r_i\) 个餐巾单独进行结账。这样就限制了到这一天的干净餐巾的数量。

同样，如果仅仅用一个点无法完成这些操作。所以考虑将第 \(i\) 天拆成 “今天需要的餐巾（结账）” \(i_1\) 与 “今天需要清洗的 ” \(i_2\)。

那么存在建图的方案，

连接一条由源点 \(S\) 到点 \(u_1\) 的流量为 \(+\infty\)，费用为 \(p\) 的边。（购买得到）
由点 \(u_1\) 连向汇点 \(T\) 进行每一天的结账。
连接一条由源点 \(S\) 到点 \(u_2\) 的流量为 \(r_i\) ，费用为 \(0\) 的边，以补充上一步流出的餐巾数。
点 \(u_2\) 作为 “需要清洗的” 步骤，连向三个地方：1、快洗后的一天 \(a_1\)，慢洗后的一天\(b_1\)，以及扔给下一天 \((u+1)_2\)

这种方案满足了每天恰好会花费一定数量的餐巾的限制。

# 软件补丁问题

[link]初读题目，由于一个部分仅会出现两种情况，正确或者错误。设 \((1,0)\)，表示第 \(1\) 个错误不存在（正确），第 \(2\) 个错误存在。那所以对于起初的软件可以表示为 \((1,1,\dots,1)\)。

而对于一个补丁来说，可以由一个存在错误的状态转移到另一个存在错误的状态，同时花费时间。最终使这个状态全部为 \((0,0,\dots,0)\)。

这很容易的让人想到最短路算法，没错这是一个最小转移代价的最短路题目，利用状态压缩简化。

如何建边？

由于一个补丁的限制比较严苛，存在 \(B_1,B_2,F_1,F_2\) 四个状态。

设当前状态为 \(x\)，在使用位运算时，

若 x and B1 == B1 时，就表示 \(x\) 存在 \(B_1\) 的所有错误。
若 x and B2 == 0 时，就表示 \(x\) 中并不存在 \(B_2\) 的错误。

因为 \(x\) 可能存在不属于 \(F_1\) 的错误，我们会清除掉这些错误，不妨让这个状态先拥有 \(F_1\) 的所有状态（or），再进行异或xor操作清除。

新状态 y = ((x or F1) xor F1) xor F2;

将其分为 \(n+1\) 点，表示每一个错误状态，若这个补丁在该点是可用的，就将该点连到改变状态后的点，其边权为所用时间。

# 数字梯形问题

[link]这个题目被分为了三个部分，总之来讲还是一个最大权不相交路径问题，这条路径很明显是从最顶端到最底端的一条路径。

最长路可以对一条由起点到终点的路径求最大边权，而此题存在多条路径，由此可以想到最大费用最大流。

从梯形的顶至底的 \(m\) 条路径互不相交

路径不相交，即为点不相交，边不相交。对于边来说可以将流量设置为 \(1\)，费用为 \(0\) 的边。

而对于点来讲，权值是位于点上的，这时候其实就可以想到拆点的方法，将点权转移到边权，并将流量设置为 \(1\)。

而对于规则 \(2, 3\) 来讲，仅仅是限制了点的流量 或 边的流量。

至于流网络的源点与汇点，必然是连在梯形的顶部所有的点，与底部所有的点上，流量均为 \(1\)，而费用均为 \(0\) 的边。而对于 \(m\) 条路径的限制，可由一个备用源点 \(S'\) 连到原源点上，流量为 \(m\)，作为限流的作用。

# 运输问题

[link]由于零售商店需要来自仓库的货物 \(b_i\)个，存在第 \(i\) 个仓库到第 \(j\) 个零售商店费用为 \(c_{i,j}\) 。这种既存在费用限制，又存在数量限制的模型，很easy想到的就是网络费用流的模型。

那么这个建图的方式也就呼之欲出了。

由仓库可向零售商店连接一条流量为 \(+\infty\)，费用为 \(c_{i,j}\) 的边。
共有 \(m\) 个仓库，每个需要 \(a_i\) 个单位的货物，这种限制可由源点 \(S\)，进行限流，连接一条流量为 \(a_i\)，费用为 \(0\) 的边。
由汇点接收所有零售商店的货物，因为每个商店只需要 \(b_i\) 个货物，所以由商店向汇点连接一条流量为 \(b_i\)，费用为 \(0\) 的边。

然后就可以分别算出最大费用与最小费用了。

# 分配问题

[link]对于该题，共有 \(n\) 个工作分配与 \(n\) 个人做，而二者之间并不存在什么制约关系，最多是一个工作只能一个人做罢了。

那么这个模型就与二分图并无两样了，但其中有增加了边权的限制，这个模型就可以为二分图最佳匹配，

由于网络流的最大流可以完美的解决二分图匹配问题（详见[飞行员配对方案问题](# # 飞行员配对方案问题)），而现在增加了边权的限制，就如同最大流模型上增加了费用，变成了费用最大流问题是相同的。

由每个工作连向每个人一条流量为 \(1\) （一条匹配），费用为 \(c\) 的边。
由源点流向工作，由员工流向汇点，流量为 \(1\)，费用为 \(0\) 的边。

模型虽简单，却非常之经典。

# 负载平衡问题

[link]读到该题，一股思路涌现，—— 贪心！（最小代价供求问题）

该题的确可以用贪心解过，但是我们分析另一种思路，由于存在可以由相邻的仓库之间搬运，可以理解为相邻仓库存在连边。

对于每个仓库，它开始拥有 \(k_i\) 的货物，到最后会拥有 \(x\) 的货物。

由题意可知，\(\frac{1}{n}\sum_{i=1}^{n} k_i=x\)，即先前的货物的总量 \(=\) 最后货物的总量

可以设立一个源点连向仓库 \(i\)，流量为 \(k_i\) 的边，作为最先存在的货物，设立一个汇点，由仓库连向，流量为 \(x\)，表明最后这个仓库拥有 \(x\) 的货物，其费用均为 \(0\)。
而两两相邻的仓库之间存在边，其流量为 \(+\infty\) ，费用为 \(1\)。

这种建图的方式，可以完美的解决了最后使所有的仓库的数量相等的限制，也比较好理解。

当然存在另一种建图方式，

将 \(k_i-x> 0\) 的仓库，由源点 \(S\) 连入，流量为 \(k_i-x\)，费用为 \(0\)。
将 \(k_i-x<0\) 的仓库，连入汇点 \(T\)，使其流量为 \(x-k_i\)，费用为 \(0\)。

这种方式，将个别仓库多的货物流向缺少货物的仓库，然后计算费用。

# 最长k可重区间集问题

# 星际转移问题

[link]由题意可以发现每个太空船的停靠周期可能是不相同的，所以无法一步进行完全转移。而太空船是到达月球的唯一方法，对于太空船，具有周期性（受时间影响）。

我们由时间作为条件，可以发现，当第 \(i\) 时到第 \(i +1\) 时：

位于第 \(i\) 时第 \(j\) 号太空站的人员，可能会到达第 \(i+1\) 时第 \(j\) 号太空站。（即未进行移动）
位于第 \(i\) 时第 \(j\) 号太空站的人员，可能会到达第 \(i+1\) 时第 \(k\) 号太空站，\(k\) 将会受到太空船的影响。

由此我们可以想到这可能是一张分层图最大流（人数），为网络判定。

将源点 \(S\) 连向第 \(1\) 时间的地球上，流量为总人数。

我们枚举时间 \(t\)，将第 \(t-1\) 时间的点连到第 \(t\) 时间的点，会存在两种情况

不管有没有太空船可坐，都可以由点 \(u_{t-1}\) 连向点 \(u_t\)，流量为 \(+\infty\)。

有太空船可坐，并由点 \(u_{t-1}\) 连向点 \(k_t\)，流量为 \(h_i\)（太空船人数限制）。

将汇点连到每个时间的月球上，判断其最终流量是否与总人数相等即可。

由于可能存在无法到达的情况，那这种情况是什么呢，即为所有的太空船都不会经过月球（可用并查集判断是否连通）。

# 孤岛营救问题

[link]由于这道题目涉及的知识面比较单一，可以easy地考虑到图论的想法。求出最短时间，那么很有可能是求解其最短路径。

但是对于这个题目来说，具有门和钥匙的限制，是不好在同一张图中解决的。（当然你也可以使用搜索大法，将状态全部存起来）。

由于这个图受门和钥匙类型的限制，而这个限制比较小（\(p\le10\)），可以考虑 分层与状压 。

将图分为 \(2^{p}+1\) 层，每层的编号可以为该层的钥匙状态。
若在 \(x\) 层得到了新的钥匙，可以将其连到拥有新钥匙的第 \(y\) 层，边权为 \(0\)，位置不变。
若拥有该门类型的钥匙，即可以通过。

我们由第 \(0\) 层，即没有任何钥匙的 \((1,1)\) 位置跑最短路。

然后对于每一层的 \((n,m)\) 位置取得一个最小值，即为答案。（也可以建立汇点直接连接，边权为 \(0\)）。

# 航空路线问题

[link]很明显，这个题已经告诉了你这个图长啥样，但是对于解决问题还是远远不够的。

从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。

对于这条限制（误导信息）的理解极为重要，其实不管对于从东到西，还是从西向东，总之是在两端城市间晃悠。

所以这个问题可以化为求两个最长不相交路径的长度，其中起点与终点相交（可重复2遍）。

因为点的经过次数的限制，那么可以考虑将这个点进行拆点操作，用最大流解决，使其流量为 \(1\)。（起点与终点为 \(2\)）

最后对流量为 \(0\) 的边遍历两遍输出路径即可。

可能出现只能飞一遍的情况，（最终流量至于 \(1\) ）这种情况视为无解。

# 汽车加油行驶问题

[link]对于这样的具有限制的，且限制较小的最短路问题，可以考虑将这个限制变成新的一维，将原本的二维网格变为新的三维图形，即分层。

对于该题，很明显的是一道最短路问题（BFS解决!!），由 \((1,1)\) 到达 \((n,n)\) 的最短花费（路径）。

但是我们想如果在 \((x,y)\) 处建立了油库，那么就很难判断是否汽车到这里时是油库建立前还是之后了。

其中由于新增了油量的限制，所以可以把最短路的 \(dis_{i,j}\) 状态变为 \(dis_{i,j,k}\) 的三维。这样也就可以解决如果在一张图中如何不错误的建立油库，并加油的问题。

（当我们动规状态用不了时，也可以考虑多加几维\ww）

然后对于每个时期的状态就有了很好的转移，设 \(0\le w\le k\)。

对于油量 \(k \neq 0\) 时，汽车可沿 \(X\) 轴或 \(Y\) 轴进行移动。即

\[(i,j,w)\xrightarrow{B}(i-1,j,w-1)\ 或\ (i,j-1,w-1)\\ (i,j,w)\xrightarrow{0}(i+1,j,w-1)\ 或\ (i,j+1,w-1) \]
但当遇到加油站时，汽车需要严格的进行加油操作，即

\[(i,j,w)\xrightarrow{A}(i,j,k) \]
往往我们都会遇到油量变为 \(0\) 的情况，又因为题目告诉我们说油量为 \(0\) 时，必须建油库，所以对于任意的 \((i,j,0)\) 状态都会存在一条连向 \((i,j,k)\) 的边。

\[(i,j,0)\xrightarrow{A+C}(i,j,k) \]

既然分完层了，那么不管当流量是什么的时候（ \(0\) 也可以）只要到达 \((n,n)\) 就算到达，那么对于所有的 \((n,n,i)\) 的位置的最短路径就是答案，当然开始是从 \((1,1,k)\) 开始的。

# 深海机器人问题

[link]由于该题是求最优移动问题，即线性规划问题。（当然这个题目不能用最短路做）

由于最短路只能跑一次（多跑几次也一样），也就是只能允许一个机器人跑一遍。

那么多跑几遍？也不是不行。因为最短路的图相当于一个流量只有 \(1\) 的流网络，既然这个题目扩大了其“流量”，那么也就可以使用费用流解决。

由于已经给出了边权，那么对于每个边权只能有一个机器人接收，那么说，这条边的流量只能为 \(1\) 。

但是题目中有说过 而且多个深海机器人可以在同一时间占据同一位置。

（那么就让这条边流量变为 \(0\) 的时候，让流量变为 \(+\infty\)，让费用变为 \(0\)）

很显然用上面的方法是行不通的，而对于改变后的边，（它完全就是一条新的边嘛），我们在建图的时候直接加进去不就好了。

由于这两条边的起始、结束点相同，而费用不同，对于最大费用流来说，肯定是先跑最大费用的边。

所以，这样做是没问题的。

# 火星探险问题

[link]该题也是求最优移动问题，即线性规划问题。

与[深海机器人问题](# # 深海机器人问题)同属于一类题型，但是该题的思维难度会存在微微提升。

对于该题，由于每个石块的位置存在于点上，这对于流网络来讲，是极其不友好的。所以可以考虑将点进行拆点，点权边化。

而由于存在障碍物，即无法达到此处，也就是不存在该边。

最后对于方案的输出，不用多说，沿着流量为 \(0\) 的边深搜即可。

# 骑士共存问题

[link]该题目与[方格取数问题](# # 方格取数问题)²的题意极其相像，而做法也是大同小异。

同样每个点会与其周围 \(8\) 个点产生制约关系，同样可以将其理解为边。

我们通过手推一个 \((5\times 5)\) 的矩阵（……）

可以发现同样是具有奇偶性相同的点将不会互斥，其中不会存在连边，就像是二分图。而我们的想法是求出最多的不存在连边的点，即二分图最大独立集。

而二分图最大独立集与总点数和最大匹配的差相等，也可以用网络流的最小割解决²。

对于最小割来讲，可以将奇偶性不同的点分为两部分，其中存在边相连（将流量设置为 \(+\infty\)，防止被割掉的不会是点）。

其他由源点到一组点，由另一组点到汇点连边，流量为 \(1\)。

# 最长k可重线段集问题

# 机器人路径规划问题

[link]这个题呀。。。

后续[wll24] All code and 题目链接

编号	题目名称	类型
1	飞行员配对方案问题
2	太空飞行计划问题
3	最小路径覆盖问题
4	魔术球问题
5	圆桌问题
6	最长不下降子序列问题
7	试题库问题
8	方格取数问题
9	餐巾计划问题
10	软件补丁问题
11	数字梯形问题
12	运输问题
13	分配问题
14	负载平衡问题
15	最长k可重区间集问题
16	星际转移问题
17	孤岛营救问题
18	航空路线问题
19	汽车加油行驶问题
20	深海机器人问题
21	火星探险问题
22	骑士共存问题
23	最长k可重线段集问题
24	机器人路径规划问题

标签：24,路径,匹配,源点,网络,流量,问题,wll24,link
From： https://www.cnblogs.com/Cnghit/p/17058612.html

网络流24题（wll24）