0%

2.21网络流

ARC107F

题意

给出一张$n$个点,$m$条边的无向图,每个点有点权$A_i,B_i$。你可以选择若干个点删掉,代价为它们的$A_i$之和,然后对于剩下的每个连通块,获得的分数为其$B_i$之和的绝对值。

最大化收益减去代价。

题解

对于保留下来的每一条边,这条边连接的两个端点的$B_i$符号必然相同。注意到最后要最大化收益,因此可以去掉$B_i$的绝对值,相当于我们要给每个点分配$-1,0,1$,同时保证删去$0$点之和的每个连通块内所有点的标号相同。

对于原图中的每个点$i$,拆成两个点$i,i’$,连边$s\rightarrow i\rightarrow i’\rightarrow t$。割去这三条边分别表示$1,0,-1$。即一开始我们默认所有点的权值都是$B_i$,然后根据最小割的定义给这三条边分配容量。答案就是$\sum B_i$减去最小割。

考虑如何连边。由于每个点的状态只有三种,而当一个点被删去时,与它相连的所有边产生的限制都将消失。因此,我们只需要满足,一旦某个连通块内存在一个$-1$,就意味着这个连通块内必须全部是$-1$。不需要考虑$1$的限制。

因此,对于一条边$(u,v)$,连边$u’\rightarrow v,v’\rightarrow u$,边权$\infty$。即如果$u$或者$v$为$-1$,要么另一个点被删去,要么另一个点也必须为$-1$。

Gym101471J

题意

给出一张$n$个点$m$条边的有向图,其中有两个源点$S_1,S_2$和汇点$T$。有两种液体,分别从$S_1,S_2$流入。第一种液体每单位会占用$1$的容量,第二种液体每单位会占用$v$的流量(单位可以是小数)。设这两种液体到达汇点的流量分别为$W,F$,那么最后的收益为$W^aF^{1-a}$。输出最大值。

题解

观察一下可以发现$v$是没用的,我们可以将这两种液体都当成每单位只会占用$1$的流量,最后再将收益除以$v^{1-a}$。

分别从$S_1,S_2$开始跑一遍普通的网络流,记最大流量分别为$W_{max}$和$F_{max}$。接着建一个超级源点,向$S_1,S_2$连边,可以跑出$W+F$的上界$S$。

接下来我们证明,如果记$(W,F)$为最终一组可行的流量,那么它合法当且仅当:

  • $W\leq W_{max}$
  • $F\leq F_{max}$
  • $W+F\leq S$

这三个条件显然是必要的。接下来我们证明充分性。

考虑两种可行的流量:$(S-F_{max},F_{max})$以及$(W_{max},S-W_{max})$。我们可以给这两种方案分配$\alpha,\beta$的系数,只需要满足$\alpha+\beta\leq 1$。此时每条边最终的流量必然没有超过容量上界。运用向量的知识即可发现可以得到所有满足上述条件的$(F,W)$。

问题转化为了一个简单的不等式问题:如何分配$\alpha,\beta$使得$W^aF^{1-a}$最大。

运用简单的求导知识可得$[\alpha^a(1-\alpha)^{1-a}]’=0$时$\alpha$最优,化简得$\alpha=a$。即$\frac WF=\frac{a}{1-a}$时答案最优。

CF1307G

题意

一张有向图,$q$次询问,每次给出$x_i$,可以给每条边的边权加上一个数,使得加的数之和不超过$x_i$,最大化$1$到$n$的最短路。

题解

先考虑一次询问怎么做。

它看起来就非常的线性规划,首先将原问题转化为线性规划问题。

设原来的边权为$w_{u,v}$,加的数为$a_{u,v}$,我们想要判断答案能否超过$D$,那么有

最小化

满足约束

将第一个限制移项变为$d_u-d_v+a_{u,v}\geq -w_{u,v}$。于是我们得到了一个需要初始化的线性规划。

显然我们不可能每次都重新跑一遍这个线性规划,考虑将它转成对偶。

此时我们给原来每个方程分配一个新的变量$b_{u,v}$,给$d_n-d_1$这个方程分配变量$f$,可以得到对偶线性规划:

最大化

满足约束

可以发现,它长得非常像费用流。

直接在原图上跑单路增广费用流,容易发现最终的最小费用是一个关于流量的分段一次函数,断点是每次增广之后的当前流量。

$D$与边权是无关的,于是我们可以在所有询问之前先求出流量为$i$时的最小费用,然后大概是一个斜率优化。

CF1383F

题意

给出一张$n$个点$m$条边的有向图,其中有$k$条边是特殊边。$q$次询问,每次会给这$k$条边重新分配容量,问$1$到$n$的最大流。

题解

最大流等于最小割,因此我们可以暴力枚举这$k$条边割的情况,因此一共只有$2^k$种本质不同的最大流。

复杂度为$O(flow\times 2^k+2^k\times q)$。

需要预处理保留这$k$条边的每个子集时的最大流,直接跑很难过,考虑优化

第一种优化是先将这$k$条边全部去掉,跑一遍最大流,然后仅保留残量网络。接下来每次在残量网络上增广。

第二种优化是采用优秀的转移方式,可以使用类似格雷码的方式,每次在原来网络的基础上加入一条边。