1.22更新

Nortrom · 2022-01-20 15:54:04 · 个人记录

方格取数问题

引子：二分图强化版，要注意两边阵营的点建图时是单向INF，由s->t单向边，反向边为0

限制条件：如果要取某一个方格，那么禁止取相邻的四个方格，不限制其它所有方格。

解决：

能删掉一个元素，表示不取这个方格；

删掉的代价为方格的权值；

要么删掉的总是保证策略最优的，要么能反悔；

最终状态为：没有互斥的方格了。

二分图的另一个点集连向超级汇，边权还是点权。删边也表示不取此点。

二分图内部的边，连接着互斥的点。边权全部赋为 inf，以保证在最小割中不被删 注意：若为双向INF则结果为36分，因为该流量为单向，即权值最大时，而且双INF会容易出现负边权

[国家集训队]happiness

引子：模型很难想，尤其是在没接触过类似的模型时。该类型不同于分阵营完全割点，该模型是删去流量最小的边， 可以是两边的部分边（实质上是因为合并两个相同边时会有附加权值，难以用一条边表示,所以新建一条边） 在比较的同时保留有附加权值的或舍去无附加权值的。

正确性：一个点只能对应一个科目（文科或理科），当某个点选择了文科 s，那么它向理科 t 的边都应该要被断开。考虑哪些边会被断开：首先是它直接连向 t 的边，其次是它和别的点组合连向 t 的边，这样一来，这些边在网络图的割中是有贡献的，意味着这些边的容量在答案中没有贡献

比较好理解的思路

从源点s向每个点连选文科的价值，从每个点向汇点t连选理科的价值，割那条表示不选哪科，这样可以保证每个人不选文就选理

限制： 只要点对(i,j)中至少有一个不选文（理科同理），我们就要减去同选文的价值。

解决方案： 可以新建一个节点x，从s向x连容量为i,j同选文的价值，之后从x向i,j连容量为inf的边。 图修改一下，就是文理分科 的图

题解里一种思路（方程思想）

思路来源

狼和羊的故事

引子：非常好的最小割理解问题（分阵营连源点汇点、路径割点的深度理解）如：边权为INF的边视为不割边、同阵营的边在此题互相连无影响（因为割点时不会割它）

思路

(1)数据范围较小：100%的数据n,m≤100

(2)两个势力(尽管有中立)二分图->网络流 但这不是完全是二分图

※(3)额外发现 首先我们可以发现狼和羊的本质是相同的 即不管让1为羊或2为羊，对结果没有影响，两边割的边最小值结果相同

建两个超级点，分别与羊和狼连边 只需在砍去一些边之后，保证一个超级点无法走到另一个超级点就好了

建图

至于容量，当然是1，因为一个栏杆对应的就是一个单位花费，而源点和汇点向狼和羊连边的容量自然就是INF，一个极大值。羊现在可以根据路线 羊->中立地区->狼 准确的送到狼的嘴里 所以现在我们要保证无法从 羊->中立地区->狼 即 源点->羊->中立地区->狼->汇点

所以羊与中立地区，中立地区与狼(注意顺序) 也要连边

题解的总结

其实整条路径是这样的： 源点->羊->中立地区->中立地区->狼->汇点

我们不能把源点和羊的边砍掉，也不能把狼和汇点的边砍掉，所以这些边的容量为极大值。

我们只能任意砍掉其它的边，使得这条路径不通，而砍掉一条边的代价为1，所以这些边的容量为1

所以整个过程就是求最小割

我们要连的边有：

1. 源点 −INF−> 羊
2. 羊 −1−> 狼
3. 狼 −INF−> 汇点
4. 羊 −1−> 中立地区
5. 中立地区 −1−> 中立地区
6. 中立地区 −1−> 狼

   善意的投票/冠军调查

   引子：割点，但不一定能想到怎么处理，其实刚开始我也没想清楚，后来我画图时发现其实只有意见不同的能影响到，反而会干扰到结果

   思路：

   同意的点：连接超源（s->x边权为1，表示与自己冲突）

不同意的点：连接超汇（y->t边权为1，表示与自己冲突）

同意的点与不同意的点间若为朋友关系则互连（正边与反向边均为1，因为两边同时对互相有影响） 那此时，不难发现，我们所要使整个状态的“冲突”最小，就是使该图的S部分和T部分分割开，即求该图的最小割； 又因最小割等于最大流即求最大流

最小路径覆盖问题

引子：

其实一开始我是用欧拉回路统计出度和入度的，不过模型有问题。其不严谨性在于任意一个点都有可能是该集合的起点，并非只有入度为0的点才算起点，图例：

• 其实不难看出,当我用欧拉回路求入读时会有以下问题： （1）此时图内只有1为起点，可形成集合时，却有两个，12和3，证明通过欧拉回路找起点方案不可行 （2）每次隔开元素时会形成新的起点，那么此时就已经不可成立

  题解提供思路：二分图

  二分图，在网络流上体现为：

最小路径覆盖=点的总数-网络最大流

拆点后源点向1~n连接权为1的边，n+1~2n向汇点连权为1的边。

对于原图中相连的两个点x->y，二分图中体现为x->y+n。 （拆点常规操作，但在这里x+n为入点，x可以相当于该点的末端） 最后的方案可以利用残量网络用并查集维护。

即从1到n枚举，从每个点向外扫一圈，如果有流从这条边经过，并流向y+n，则合并x与y。

然后n^2输出方案即可。

以上为题解思路

• 关键：拆点 （其实还是因为拆点后点自身就可获得一个权值，不然就无法统计通过了多少个点，亦或是无法确定某个连通集合有多少个点（此时点数=流量大小），

（当然拆完点后就很多时候可以考虑成二分图） 将每个点拆成两个，一个入点，一个出点 （单向出或单向入的时候可以考虑？）

如果原图中两个点之间有一条有向边，那么就将拆点后的图该点的出点连一条容量为1的边到另一点的入点（其实可涉及到最大匹配konign定理）

然后建立一个超级源点，超级汇点，把超源向每个出点连边，入点向超汇连边，然后跑最大流。

每条路径的开头就是入点中没有匹配的点（其实实质就是最流量为0，流到汇点的流量少于总的点数），跑最大流的时候记录一下每个入点对应的出点（因为能统计到的点是从超源开始的，到超汇结束的，而不能统计到的点刚好是隔离开的，单独的点）