网络流24题集合
网络流 24 的题目还比较有意思，涵盖了许多常见套路，值得刷一边。只是有些题的输入输出实在是太屑了（恼）。
搭配飞行员
一架飞机要一个正驾驶和一个副驾驶，只有特定的正副驾驶组合才能飞，问最大起飞个数。
十分基本的二分图匹配。
太空飞行计划
有一堆仪器和一堆实验，每个实验要求实验室里有某些仪器才能做。买仪器要花钱，做实验能赚钱，问最多赚多少钱。要求输出方案。
常见思路：把最大可选择转化为最小可不选择。
建最小割模型，左边仪器价格边，割掉表示买仪器，右边实验收益边，割掉表示不做实验，中间无穷边。如果有一个实验不割表示做，而要求的某个仪器不割表示不买，中间的无穷边就导通，表示方案不合法。
最后用实验总收益减去最小负收益得到答案。
输出方案想不太清楚，题解说统计没有被割掉的实验边，就表示这些实验选做，看上去莫得问题但总感觉怪怪的。
吐槽：这题的输入输出真是人间之屑。
最小路径覆盖
给一个 DAG ，让你用最少的路径条数覆盖所有点，路径之间不能交叉。
似乎比较多问题可以转化到这个模型，需要熟悉。
还是老套路，最小可选转化为最大可不选。这道题里就是最小路径数转化为最多可以连接的节点对数。
所以左边所有点连 1 边，右边是另一组所有点，连 1 边，表示每个点最多出一次入一次。中间是有向图中的边，入点是左边，出点是右边，表示一个可连接点对。
最后用总点数减去最多可连接点数就得到答案。因为每连接一对点就少一条链。
魔术球
有 n 个柱子，现往上依次放入编号为 1, 2, 3, 4, … 的球，要求：
- 每次只能在某跟柱子的最上面放球
- 同一根柱子中，相邻两个球的和为完全平方数
问你最多能放多少个球，并输出方案。
直接最大流难做，应该转化为可行性问题。一个柱子本质就是一个链表，每个球都指向自己下面的球。柱子本身可以抽象成一个节点，任何人都可以都往上连，表示新开一个节点。除了柱子就只能连向值比自己小，而且和为完全平方数的点。这样左边是 m 个点，右边是 m 个点 + n 个柱子点，左边往右边可以放的点连边，权值为 1 。s 到左边，右边到 t 都连权值为 1 的边，表示一个点只能用一次。如果跑满流就表示存在合法解，这其实也是个完美匹配问题。
二分答案找最优解可能太慢，可以每次在残余网络的基础上额外左右加两个点和若干边，然后再执行 dinic ，如果流量增量为 1 就表示此答案合法，可以继续往上加。
圆桌聚餐
有来自 个不同单位的人吃饭，每个单位有 个人。餐厅有 张桌，每张桌有 个坐。
现要求找出方案，使没有两个同一单位的人在同一桌就餐，且所有人都能吃上饭。
很基本的建模。
二分图，左边是单位，右边是桌，权值分别是人数和坐数，然后每个单位到桌连 1 边，表示一个单位最多有一个人去某个桌。
直接跑最大流，满流就表示有方案。再根据中间边的剩余流量输出方案，如果单位 到 桌 的边满流，就表示 单位派了一个人去 桌。
方格取数
在一个 的棋盘中，每个方格有一个正整数。
现从方格中取数，使任意 2 个数所在方格中没有公共边，且取出的数的总和最大。
注意棋盘题，棋盘是一个非常套路的二分图模型。
黑白染色之后，白色在左边，黑色在右边，就形成一个二分图。二分图左右两边某些点不能同时选。
从源到左边和从右边到汇都是格子里的值，左右两边冲突点之间连无穷边。
这样割掉一个格子就表示不选，如果有两个冲突点都没有割，他们中间的无穷边就导通，表示方案不合法。
最小割求出最小不选点，用总数减去就是答案。
这道题虽然也用到了常见套路最大转最小，但反而不太需要刻意思考这方面。只要首先注意到棋盘图转二分图，很自然就想到最小割。