网络流 - 模型_LCA
JueFan 一只绝帆

网络流

经典模型

二分图最大匹配/最大权匹配

最大权匹配等价于拆点后的最大匹配,S→axx→∞y→ayTS\xrightarrow{a_x} x\xrightarrow{\infty} y\xrightarrow{a_y} T。

二分图的一些东西,最大匹配 == 最小点覆盖 =n −=n\ - 最大独立集 == n −n\ - 最小边覆盖。

最小链覆盖/最小路径覆盖

拆成入点出点,每条边都是出点向入点连边,然后变成最大匹配,答案是 n −n\ - 最大匹配。

理解起来就是初始每个点自己是一条路径,每个匹配相当于接起来两条路径。

若路径之间可以重复点,那相当于不能重复点但是能往前跳任意步,传递闭包之后再做就可以了。

也可以不传递闭包,只需要每个点入点向自己的出点连 ∞\infty 的边,表示可以跨过这个点。

最长反链:偏序集(传递闭包图)上两两不可达的最大集合,它等于最小链覆盖。

偏序集最大独立集

等于最长反链。

偏序集最大权独立集:[ABC354G] Select Strings,等价于拆点后的最大独立集,然后一路转成 ∑ai −\sum a_i\ - 最大权匹配。

最小割

文理分科/带权2-sat

每个点要么文要么理,同桌之间若干组合会产生价值,可以用 S→inf⁡x→inf⁡TS\xrightarrow\inf x\xrightarrow\inf T 的模型,inf\rm inf 是数量级介于 ∞\infty 和 cc 之间的数,使用它是为了防止为了逃避贡献同时割掉两边,两个点之间的贡献是好处理的。

等价于每个逻辑命题要么成立要么不成立,若有两个逻辑命题满足某种关系就产生某种价值。

p.s. 有一种简单的情况有更简单的图,即所有限制形如(a,ba,b 不能分家,aa 必须选文,aa 必须选理)中的一个,此时直接把必须选文的连 SS,必须选理的连 TT,不能分家的连双向边,不过这种情况似乎可以线性处理。

把价值改为 ∞\infty 就是正常的逻辑 2-sat。

2-sat 指的是 (x1∨x2)∧(x3∨,x4)∧⋯(x_1\vee x_2)\wedge (x_3\vee,x_4)\wedge\cdots,用 ∨\vee 连接的逻辑命题至多两个,但是 ∧\wedge 可以任意连接。

但有时候不仅仅 2-sat 才能用该模型,很多时候我们可以把好几种选择给拆成几个二元逻辑命题,然后证明不存在非法情况/非法情况必定不优来达成我们的目的。

例:CF1666K Kingdom Partition

给定一个无向图,你要把点分成三部分,对于一条边权为 ll 的边,设 aia_i 是点 ii 在的集合:

  • 若 au,av=1∨au,av=2a_u,a_v=1\vee a_u,a_v=2,则贡献为 2l2l。
  • 若 au=3∧(av=1 or 2)a_u=3\wedge (a_v=1\text{ or }2),则贡献为 ll。

同时强定 ax=1,ay=2a_x=1,a_y=2,求最小总贡献并构造方案。

n≤1000,m≤2000n\le 1000,m\le 2000。

三个集合,一看傻眼了。

不要急,先硬拆。

设 xi=[ai=1],yi=[ai=2]x_i=[a_i=1],y_i=[a_i=2],那非法情况是 xi=yi=1x_i=y_i=1 的情况。

根据最小割的定义,我们要最小化这个式子:

∑(u,v,w)w⋅xu⋅(1−xv)\sum_{(u,v,w)}w\cdot x_u\cdot(1-x_v)

xx 都是布尔变量,且 xS=1,xT=0x_S=1,x_T=0。

也就是说代价关于 xx 其实是一个线性的关系,根据我们的定义不难得到 [ai=3]=1−xi−yi[a_i=3]=1-x_i-y_i,那我们可以推算出 x=y=1x=y=1 的点连了一次 AA,连了一次 BB,连了 −1-1 次 CC。

称其为 DD 类点,那么其连边贡献为:

D↔A:2l+0−l=lD↔B:0+2l−l=lD↔C:l+l−0=2lD↔D:l+l−2l=0D\leftrightarrow A:2l+0-l=l\\D\leftrightarrow B:0+2l-l=l\\D\leftrightarrow C:l+l-0=2l\\D\leftrightarrow D:l+l-2l=0

你发现贡献跟 CC 一模一样,所以我们可以容忍 DD 的存在,最后把 DD 全换成 CC 就是答案。

但我们连边还要把形式变成每个布尔变量是否成立的形式,把贡献列出来:

2lxuxv+2lyuyv+l(1−xu−yu)(xv+yv)+l(1−xv−yv)(xu+yu)2lx_ux_v+2ly_uy_v+l(1-x_u-y_u)(x_v+y_v)+l(1-x_v-y_v)(x_u+y_u)

暴力展开化简(手推柿子别写 ll,会和括号混在一起的)得到 wxu+wxv+wyu+wyv−2wxuyv−2wxvyuwx_u+wx_v+wy_u+wy_v-2wx_uy_v-2wx_vy_u。

合并可以得到 wxu(1−yv)+wxv(1−yu)+wyu(1−xv)+wyv(1−xu)wx_u(1-y_v)+wx_v(1-y_u)+wy_u(1-x_v)+wy_v(1-x_u),当然你也可以硬使用上面的式子,先把答案减掉 4w4w,然后只要没选 xuyvx_uy_v 就获得 2w2w,另一边同理。

观察到限制全部形如不能分家,此时可以使用上面说的简单模型。

切糕模型

类似修车,我们将每个点的每个值拆点,用一条链串起来,割哪条就表示选了哪个值,然后对于若 x≥ax\ge a,则 y≥by\ge b 这样的限制就可以使用 (x,a)→(y,b)(x,a)\to(y,b)。

例:[ARC107F] Sum of Abs

NN 个点 MM 条边的无向图,每个点有两个权值 AiA_i 和 BiB_i。可以用 AiA_i 的代价删除第 ii 个节点。并删除与这个点相连的边。一个极大连通块的权值定义为 BiB_i 的权值和的绝对值。

删除一些节点后,收益定义为所有极大连通块权值之和减去代价和。求最大的可能收益。

n,m≤300n,m\le 300。

每个点最终的贡献有三种:

  • 被删了:−ai-a_i。
  • 正贡献:bib_i。
  • 负贡献:−bi-b_i。

我们发现绝对值并不重要,只需要同一个连通块里的点(有边相连的点)的正负性一样即可。

所以我们使用切糕模型,用 正——删——负 串起三个点,只需限制一个人是负时另一个人不能是正。

负贡献问题并不大,可以整体偏移。

最小费用流

CF1288F Red-Blue Graph

有一张二分图,左边有 n1n_1 个点,右边有 n2n_2 个点,mm 条边。每个点可能有一种颜色 R 或者 B,也可能没有,也就是 U。现在要给一些边染色,把边染成 R 要花费 rr 的代价,把边染成 B 要花费 bb 的代价,要求对于每个颜色为 R 的点,与之相邻的边中 R 的边严格多于 B 的边;对于每个颜色为 B 的点,与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案,输出任意一种,无解输出 −1-1。其中 1≤n1,n2,m,r,b≤2001 \le n_1, n_2, m, r, b \le 200。

注意边可以不染,此时不消耗任何代价。

若我们用流量来表示红蓝边的数量,则本题显然不是最大流,也不是最小费用最大流,所以我们要按照最小费用流去想。

这种严格多于很好搞,点是红的就 S→xS\to x 流 ≥1\ge 1 的流量,点是蓝的就 x→Tx\to T 流 ≥1\ge 1 的流量,红红/红灰/蓝蓝/蓝灰相当于用价钱“购买”流量,红蓝边相当于流量的转移。

跑有源汇上下界最小费用流即可。

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量