DDOSvoid's Blog

简要题意：有 $n$ 个学生，$m$ 个学习小组，每个学生最多只能参加 $k$ 个学习小组且每个学生只能参加某些学习小组，学生参加第 $i$ 学习小组需要付出 $b_i$ 的代价，若有 $x$ 个学生参加第 $i$ 个学习小组，则能获得 $a_i\times x^2$ 的价值，求参与学生尽量多的情况下，最小付出多少支出

$n\le 100,k\le m\le 90$

简要题解：注意到边的费用随着流量增加而增加，且增加的数值是单增的，所以我们考虑拆边

另外注意到最大流的要求不是参加每个学习小组的学生的个数总和，而是参加了学习小组的学生个数，这里我们的解决方案是再连一条 $i$ 到 $t$ 的容量为 $k-1$，费用为 $0$ 的边

$s$ 连学生 $i$，容量为 $k$，费用为 $0$

学生 $i$ 连 $t$，容量为 $k-1$，费用为 $0$

学生 $i$ 连学习小组 $j$，容量为 $1$，费用为 $-b[j]$

学习小组 $j$ 连 $t$，共有 $n$ 条边，第 $i$ 条边容量为 $1$，费用为 $(2i-1)\times a_j$

Luogu P4209 学习小组

最大流的限制为每个点至少选一次

简要题意：有 $n$ 个学生，$m$ 个学习小组，每个学生最多只能参加 $k$ 个学习小组且每个学生只能参加某些学习小组，学生参加第 $i$ 学习小组需要付出 $b_i$ 的代价，若有 $x$ 个学生参加第 $i$ 个学习小组，则能获得 $a_i\times x^2$ 的价值，求参与学生尽量多的情况下，最小付出多少支出

$n\le 100,k\le m\le 90$

简要题解：

注意到最大流的要求不是参加每个学习小组的学生的个数总和，而是参加了学习小组的学生个数，这里我们的解决方案是再连一条 $i$ 到 $t$ 的容量为 $k-1$，费用为 $0$ 的边

Luogu P4209 学习小组

二分

二分答案之后通过网络流判断是否可行

Luogu P3425 [POI2005]KOS-Dicing

简要题意：给定一个 $a\times b$ 的四连通网格图，有 $n$ 个起点和 $n$ 个终点，现在有 $n$ 个人来到这 $n$ 个起点，同一时间不能有两个人在同一个点，每个时刻每个人可以选择移动或者停止，一个人来到终点可以随时选择离开，每个终点只能使用一次，求最少多长时间所有人都离开

$a\times b \le 100,n\le 100$

简要题解：注意到最多需要花 $a\times b$ 的时间，我们考虑二分时间 $t$，然后将每个位置拆成 $(t+1)$ 个时间，拆点之后因为每个点只能经过一次，所以还要再拆一次

至于输出路径，因为所有边的容量都为 $1$，所以我们直接对于所有起点 $dfs$ 即可，路径是唯一的

$s$ 连 $(s_x,s_y,0)$，容量为 $1$

对于所有 $k\in[0,t]$，$(x_u,y_u,k)$ 连 $(x_u,y_u,k)’$，容量为 $1$

对于所有 $k\in [0,t-1]$，$(x_u,y_u,k)’$ 连 $(x_{v},y_{v},k+1)$，容量为 $1$

$(x_u,y_u,t)$ 连 $t$，容量为 $1$

The 2021 ICPC Asia Shenyang Regional Contest D Cross the Maze

最小割

最小点割

简要题意：给定一张 $n$ 个点 $m$ 条边的无向图和起点 $s$ 以及终点 $t$，求最少删掉几个点使得 $s$ 和 $t$ 不在连通

$n\le 100,m\le 600$

简要题解：

$u$ 连 $u’$，容量为 $1$

原图中的双向边，$u’$ 连 $v$，$v’$ 连 $u$，容量均为 $\infty$

Luogu P1345 [USACO5.4]奶牛的电信Telecowmunication

最小割基本应用，将图分成两部分

简要题意：给定一张 $n\times m$ 的四连通网格图，每个点属于狼、羊和空地三者之一，空地可以连接羊和狼的领地，求最少需要割掉多少条边，使得狼和羊分开

$n,m\le 100$

简要题解：注意到要割掉的边一定是羊空地狼

$s$ 连羊，容量为 $\infty$

羊连空地/羊，容量为 $1$

羊/空地连狼，容量为 $1$

狼连 $t$，容量为 $\infty$

Luogu P2598 [ZJOI2009]狼和羊的故事

最大权闭合子图

简要题意：现在有 $n$ 个实验和 $m$ 个仪器，每个实验都需要配备某些仪器才可以使用，第 $i$ 个实验完成可以获得 $a_i$ 的收益，购买第 $i$ 个仪器需要 $b_i$ 的代价，每个仪器购买之后可以使用多次，求最大收益并输出方案

$n,m \le 50$

简要题解：最大权闭合子图，我们考虑最小割，最终与 $s$ 相连表示选择，与 $t$ 相连表示不选择

$s$ 连 $u$，容量为 $a[u]$

原图中的边，$u$ 连 $v$，容量为 $\infty$

$v$ 连 $t$，容量为 $b[v]$

Luogu P2762 太空飞行计划问题
简要题意：给定一个二维平面，平面上有 $n$ 个白点，第 $i$ 个白点的坐标为 $(x_i,y_i)$，其能传输的范围为 $r_i$，收益为 $s_i$，第 $i$ 个点能传输到第 $j$ 个点，当且仅当两点之间的欧几里得距离小于等于 $r_i$，现在要将某些点涂黑，如果染黑每个点则必须将其能到达的点都染黑，染黑一个点能得到它的收益，求最大收益

$n\le 100$

简要题解：注意到原图是有向图，且一个强连通分量必须同时选，我们缩点后得到一个 $DAG$，然后我们传递闭包，能够发现，现在我们选一个点需要选它连出去的所有点

容易发现这个东西非常像是最大权闭合子图的模型，我们将点分成正权点和负权点，起点连正权点，终点连负权点，然后正权点连它需要的负权点，注意两个正权点之间的依赖关系不会影响

校内赛 5G网络

与 $s$ 和 $t$ 相连分别表示选和不选

需要注意这类题目时刻可能与二分图与联系，我们要充分利用二分图的性质

简要题意：给定 $n$ 个人，现在需要选择若干个人，雇佣第 $i$ 个人需要花费 $a_i$，对于任意两个人 $(i,j)$，如果同时雇佣会得到 $E_{i,j}$ 的收益，如果只雇佣其中一个，则会亏损 $E_{i,j}$，题目保证 $E_{i,j}=E_{j,i}$，求最大收益

$n\le 1000$

简要题解：注意到我们的总收入为 $\sum E_{i,j}$，所以我们如果不选 $u$，那么亏损为 $\sum_{i=1}^nE_{u,i}$

如果 $u$ 和 $v$ 一个选一个不选，那么损失为 $2E_{u,v}$

建图：

$s$ 连 $u$，容量为 $\sum_{i=1}^n E_{u,i}$

$u$ 连 $t$，容量为 $a_u$

$u$ 连 $v$，容量为 $2E_{u,v}$

Luogu P1791 [国家集训队]人员雇佣
简要题意：现在有一个 $n\times m$ 的四连通网格，每个位置填 $0$ 有 $a_{i,j}$ 的收益，填 $1$ 有 $b_{i,j}$ 的收益，对于每个格子 $(i,j)$ 如果它周围的格子中有 $k$ 个格子和它填的数不同，那么会有 $k\times c_{i,j}$ 收益，求最大收益

$n,m\le 100$

简要题解：注意到当两个位置所选区域不同可以获得收益，且为二分图

所以我们直接考虑将二分图两部分与 $s,t$ 的关系反过来即可

对于白点 $(i,j)$, $s$ 连 $(i,j)$，容量为 $a_{i,j}$

$(i,j)$ 连 $t$，容量为 $b_{i,j}$

对于黑点 $(i,j)$，$s$ 连 $(i,j)$，容量为 $b_{i,j}$

$(i,j)$ 连 $t$，容量为 $a_{i,j}$

对于 $(i,j)$，$(i,j)$ 连相邻的点，容量为 $c_{i,j}$，注意为双向边，因为不知道谁连着 $s$

[Luogu P1935 [国家集训队]圈地计划]
简要题意：给定一个 $n\times n\times n$ 的六连通立方体，每个位置可以填 $0$ 或 $1$，现在有些位置已经填了数，如果两个相邻的格子所填数不同则会产生 $1$ 的收益，问最大收益

$n\le 40$

简要题解：注意到依然是相反选择有收益且三维六连通依然可以二分图染色

对于黑点 $(i,j,k)$，如果已经有选择，则按照选择向 $s$ 或 $t$ 连一条容量为 $\infty$ 的边

黑点 $(i,j,k)$ 连相邻白点，容量为 $1$，注意连双向边

对于白点 $(i,j,k)$，如果已经有选择，则按照选择向 $s$ 或 $t$ 连一条容量为 $\infty$ 的边，这里注意与黑点相反

bzoj 1976 [BeiJing2010组队]能量魔方 Cube 上题的三维情况，注意到六连通三维同样可以黑白染色
简要题意：给定一张 $n\times m$ 的四连通网格图，现在要将一些格子涂黑，涂黑 $(i,j)$ 这个格子需要付出 $a_{i,j}$ 的花费，当 $(i,j)$ 被涂黑或者周围四个格子都被涂黑，则能获得 $b_{i,j}$ 收益，求最大收益

$n,m\le 40$

简要题解：考虑最小割同时注意到二分图的性质，发现最难解决的问题是或者这个条件，但其实也很好解决，直接串起来即可

对于黑点 $(i,j)$，$s$ 连 $(i,j)$，容量为 $a_{i,j}$

$(i,j)$ 连 $(i,j)’$，容量为 $b_{i,j}$

$(i,j)’$ 连周围四个点 $(x,y)$，容量为 $\infty$

对于白点 $(i,j)$，$(i,j)$ 连 $t$，容量为 $a_{i,j}$

$(i,j)’$ 连 $(i,j)$，容量为 $b_{i,j}$

周围四个点 $(x,y)$ 连 $(i,j)’$，容量为 $\infty$

【个人赛组】2021-2022年度第三届全国大学生算法设计与编程挑战赛（秋季赛）C 占座位
Luogu P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

费用流

有些题目往往用最大流仅能满足所给限制，而不能求解问题，这时候就需要用费用流

Luogu P3159 [CQOI2012]交换棋子

CF 277E Binary Tree on Plane

求费用流时，每次的最短路是单调的

Luogu P4068 [SDOI2016]数字配对由于每次最长路的值都在递减，所以我们可以直接贪心，最后一次最长路可以少流一点

二分图

DAG最小路径覆盖

简要题解：给定一张 $DAG$，求其最小路径覆盖

$n\le 150,m\le 6000$

简要题解：我们考虑这样一个建图

将原图中的所有点拆成两个点 $u$ 和 $u’$，对于原图中的有向边，$u$ 连 $v’$

然后我们考虑这张二分图的一条匹配，匹配中的每一条边都意味着原图两个路径并到了一起，即总路径数减一

所以我们要让匹配尽量大，也就是求最大匹配

至于输出方案，左边没有匹配上的点是一条路径的终点，右边没有匹配上的点是一条路径的起点

Luogu P2764 最小路径覆盖问题
简要题意：给定一张 $n\times m$ 的四连通网格图，每个点有一个权值 $a_{i,j}$，每个点只能走到周围四连通中权值严格小于自己的点，或者花费 $a_{i,j}-a_{x,y}$ 的代价从 $(i,j)$ 走到 $(x,y)$，现给定起点 $(x_0,y_0)$，求最少使用多少次第二种操作使得从起点开始经过每个点恰好一次且最终最后到起点，在最小化第二种操作的情况下，最小化代价

$n,m\le 50$

简要题解：注意到原题意相当于在给定的 $DAG$ 上选择最少的路径条数，现在的问题是如何解决代价最小

我们注意到这个代价的形式，发现非常如果选了 $k$ 条路径 $(s_i,t_i)$，那么最终的花费为 $\sum_{i=1}^ks_i-t_i$

我们考虑在将一条路径的花费拆开，发现这个东西就相当于这条路径上每条边 $(u,v)$ 的代价为 $a_u-a_v$

这样我们可以直接使用经典的 $DAG$ 最小路径覆盖来解决，将最大流改成最小费用最大流即可

Luogu P7863 「EVOI-RD1」飞鸟和蝉
简要题意：给定一个 $n$ 个点 $m$ 条边的 $DAG$，求可相交最小路径覆盖

$n\le 500,m\le 5000$

简要题解：相对于不可相交最小路径覆盖，我们现在能够选择的一条边可以是原来的多条边

所以我们拿 $floyd$ 做一个传递闭包之后再求不可相交最小路径覆盖即可

poj 2594 Treasure Exploration

最小边覆盖

简要题意：给定一个 $n \times n$ 的网格图，有一些格点之间存在边，但保证不存在变长为 $1$ 的正方形，求最多加多少条边使得仍然不存在边长为 $1$ 的正方形

$n\le 80$

简要题解：首先我们将四个格点看成一个点，那么现在有 $(n-1)\times (n-1)$ 个点，原图中格点上的边我们认为是一个障碍，那么首先原图上边界上的边我们肯定是能选则选，然后我们考虑限制，发现不存在边长为 $1$ 的正方形的条件是每个点都至少有一条边，那么我们答案我们可以转换为保留最少的边，即求一个新图的最小边覆盖

我们黑白染色后直接跑最大匹配即可

Kattis Dots and Boxes

转换成二分图，例如棋盘或者某些奇偶性

Luogu P2774 方格取数问题棋盘问题染色转换成二分图

Luogu P4068 [SDOI2016]数字配对

bzoj 1976 [BeiJing2010组队]能量魔方 Cube 三维六连通同样可以黑白染色

区间选择问题

简要题意：给定一个长度为 $n$ 的序列 $a_i$，表示每天至少需要的志愿者人数，一共有 $m$ 种志愿者可以招募，第 $i$ 类志愿者会从 $l_i$ 天工作到 $r_i$ 天，招募费用是 $c_i$ 元，求满足人数限制的情况下，最少花费多少钱

$n\le 1000,m\le 10000$

简要题解：

$s$ 连 $1$，容量为 $\infty$，费用为 $0$

$i$ 连 $i+1$，$i\in[1,n-1]$，容量为 $\infty - a[i]$，费用为 $0$

$n$ 连 $t$，容量为 $\infty-a[n]$，费用为 $0$

对于一种志愿者雇佣 $l$ 连 $r+1$，容量为 $\infty$，费用为所需要的的费用

我们稍微思考一下这样做的正确性

注意到最大流一定是 $\infty$，那么我们就一定会走志愿者边

Luogu P3980 [NOI2008]志愿者招募
简要题意：给定 $n$ 个开区间和 $k$，每个区间的价值为区间长度，要求选择尽量多的开区间，使得不存在任何一个点不覆盖了 $k$ 次以上，且选择的区间的价值最大

$n\le 500,k\le 3$

简要题解：首先为了方便，将开区间变成闭区间

我们参照志愿者招募这题的建图方法，可以得到如下建图

建图：

$s$ 连 $1$，容量为 $k$，费用为 $0$

$i$ 连 $i+1$，$i\in[1,n-1]$，容量为 $k$，费用为 $0$

$n$ 连 $t$，容量为 $k$，费用为 $0$

对于一个区间 $l$ 连 $r+1$，容量为 $1$，费用为 $-(r-l+1)$

Luogu P3358 最长k可重区间集问题
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $k,l,r$，规定每连续的 $k$ 个位置至少选 $l$ 至多选 $r$，求选出的 $a_i$ 的和的最大值是多少

$\sum n \le 3\times 10^5$

简要题解：首先考虑上界，我们利用最大流限制上界，因为限制跟区间相关，所以我们考虑将点串起来

然后我们考虑将上界的限制转换一下，我们区间看成点，这个时候区间的总点数为 $n-k+1$，那么如果选择点 $i$，相当于将区间 $[max\lbrace 1,i-k+1\rbrace,min\lbrace i,n-k+1\rbrace ]$ 都覆盖了一次，现在相当于选择若干个区间使得每个点被覆盖小于等于 $k$ 次，那么参照Luogu P3358 最长k可重区间集问题容易得到下面的建图

$s$ 连 $1$，容量为 $r$，费用为 $0$

$i$ 连 $i+1$，$i\in[1,n-k+1]$，容量为 $r$，费用为 $0$

$max\lbrace 1,i-k+1\rbrace $ 连 $min\lbrace i,n-k+1\rbrace+1$，$i\in[1,n]$，容量为 $1$，费用为 $-a[i]$

$(n-k+1)+1$ 连 $t$，容量为 $r$，费用为 $0$

至于下界，仍然是将区间看成点，参照 Luogu P3980 [NOI2008]志愿者招募，将 $i$ 与 $i+1$ 的边的容量改成 $r-l$ 即可

$s$ 连 $1$，容量为 $r$，费用为 $0$

$i$ 连 $i+1$，$i\in[1,n-k+1]$，容量为 $r-l$，费用为 $0$

$max\lbrace 1,i-k+1\rbrace $ 连 $min\lbrace i,n-k+1\rbrace+1$，$i\in[1,n]$，容量为 $1$，费用为 $-a[i]$

$(n-k+1)+1$ 连 $t$，容量为 $r$，费用为 $0$

牛客 contest 9680G 请问您要来点兔子吗利用最大流和最小割来限制上下界
简要题意：$n$ 个人参加比赛，共有 $m$ 套题，每套题有 $p$ 道题目，第 $i$ 个人答对第 $j$ 套题第 $k$ 道题目的概率为 $f_{i,j,k}$，需要注意一位选手只有答对第 $i$ 道题才能去答第 $i+1$ 题，如果一位选手答对第 $i$ 题，那么会在已得奖励的基础上再得 $c_i$ 元，现在还有 $y$ 条限制，每条限制形如第 $i$ 位选手的题目编号至少比第 $j$ 位选手大 $k$，现在需要给每个选手分配一套题目，同一套题目可以分配给多个选手，求期望奖励最少是多少

$n,m,p \le 80,y\le 1000$

简要题解：首先我们令 $g[i][j]$ 表示第 $i$ 个人做第 $j$ 套题，显然这个东西非常好算

对于求最小，我们考虑一下最小割，现在我们考虑如何处理 $(i,j,k)$ 这样的限制

能够想到对于每个人应该将 $m$ 套题拆成对应的 $m$ 个点，然后用类似区间的做法串起来

大概就是 $(i,j)$ 连 $(i,j+1)$，容量为 $g[i][j]$，$s$ 连 $(i,1)$，容量为 $\infty$，$(i,m+1)$ 连 $t$，容量为 $\infty$

这个时候我们猜一下，即对于 $(i,j,k)$，我们 $p\in[1-k,m+1-k]$，$(j,p)$ 连 $(i,p+k)$，容量为 $\infty$

但是这样我们发现限制关系不能传递，所以我们再连一种边，即 $(i,j+1)$ 连 $(i,j)$，容量为 $\infty$

所以总的建图如下：

$(i,j)$ 连 $(i,j+1)$，容量为 $g[i][j]$

$(i,j+1)$ 连 $(i,j)$，容量为 $\infty$

$s$ 连 $(i,1)$，容量为 $\infty$

$(i,m+1)$ 连 $t$，容量为 $\infty$

对于 $(i,j,k)$，我们 $p\in[1-k,m+1-k]$，$(j,p)$ 连 $(i,p+k)$，容量为 $\infty$

Luogu P6054 [RC-02] 开门大吉

棋盘模型

简要题意：给定一张 $n\times m$ 的四连通网格图，图上的点分为 $5$ 种：空地、精灵、人类、矮人、霍比特人，这四种生物的要求如下：精灵：只需要与一个邻居结盟；人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向；矮人：需要与三个邻居结盟；霍比特人：需要与四个邻居结盟，结盟关系是双向的，且只有相邻两个点才可结盟，请求出任何一种合法方案

$n,m\le 70$

简要题解：首先能够想到黑白染色变成二分图

不妨假设对于人类结盟没有必须上下和左右的要求

这时候我们可以直接这样建图，$g[i][j]$ 表示这个 $(i,j)$ 所需要的结盟数量

$s$ 连黑点 $(i,j)$，容量为 $g[i][j]$

黑点 $(i,j)$ 连周围白点，容量为 $1$

白点 $(i,j)$ 连 $t$，容量为 $g[i][j]$

对于人类结盟的要求，我们可以将人类点拆成两个点分别代表上下和左右，各有 $1$ 的容量

Luogu P6517 [CEOI2010 day1] alliances

2017-2018 ACM-ICPC Latin American Regional Programming Contest K-Keep it covered

2019 China Collegiate Programming Contest Qinhuangdao Onsite E Escape

特殊模型

修车

简要题意：有 $n$ 辆车，$m$ 个修车人，现在 $n$ 辆车都需要被修，第 $i$ 辆车被第 $j$ 个人修的时间为 $c_{i,j}$，一个人同时只能修一辆车，求顾客平均等待时间最小为多少

$n\le 60,m\le 9$

简要题解：某辆车如果被第 $i$ 个人第 $j$ 修，且第 $i$ 个人一共修 $k$ 辆车，那么它的贡献为 $(k-j+1)\times c$

也就是说对每个修车人所修的若干辆车，它们消耗的时间形如 $\sum_{i=1} i\times c_i$

我们考虑将每一个修车人拆成 $n$ 个点，对于每辆车一定被修车人 $i$ 第若干个修

所以我们考虑这样建图

$s$ 连车 $u$，容量为 $1$，费用为 $0$

车 $u$ 连修车人 $(i,j)$，容量为 $1$，费用为 $j\times a[u][i]$，表示被修车人 $i$ 第 $j$ 个修

修车人 $(i,j)$ 连 $t$，容量为 $1$，费用为 $0$

Luogu P2053 [SCOI2007]修车

餐巾计划

简要题意：现在有一个餐厅，在接下来的 $n$ 天中，第 $i$ 天需要 $r_i$ 块餐巾，购买新的餐巾的费用为 $p$，将旧餐巾送到快洗部需要 $m$ 天，费用为 $f$，送到慢洗部需要 $n(n>m)$ 天，费用为 $s$，求最小花费

$n\le 2000$

简要题解：我们大胆猜想，一定可以在保证总费用最小的情况下做到每天恰好有 $r[i]$ 条餐巾

注意到每天的餐巾有两个去向，脏餐巾留到以后用，干净的餐巾应流向 $t$

所以我们考虑一天拆成两个节点，不妨令其为上午和下午

$s$ 连 $i$，容量为 $r[i]$，费用为 $0$

$s$ 连 $i’$，容量为 $\infty$，费用为 $p$

$i’$ 连 $t$，容量为 $r[i]$，费用为 $0$

$i$ 连 $i+1$，容量为 $\infty$，费用为 $0$

$i$ 连 $(i+m)’$，容量为 $\infty$，费用为 $f$

$i$ 连 $(i+n)’$，容量为 $\infty$，费用为 $s$

Luogu P1251 餐巾计划问题