zcmimi's blog

arrow_back网络流共8篇文章

avatar
zcmimi
2019-03-06 00:03:14

题目地址:

网络流24题真的好有质量~\ (\ge \le ) /~!

进度: $\frac

avatar
zc
2020-06-15 21:47:00
查看原题

点击跳转

首先奇偶黑白染色,源点连黑点,白点连汇点,边权为点权

接着所有黑点向相邻的白点连边,边权为\infty

答案就是 点权和-最小割

avatar
zc
2020-01-18 23:37:00
查看原题

点击跳转

看到边不能重复用,n\le 200,T\le 200就可以想到网络流

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

总和减去最小割即为答案

最小割删掉的边就是要减去的值,这样就可以最小化要减去的值,即答案最大化

那我们如何构造这张图呢?

  1. ST \xrightarrow{\text{选文科的值}} (i,j) \xrightarrow{\text{选理科的值}}ED

  2. ST \xrightarrow{\text{同时选文科的额外快乐}}new,new\rightarrow(i,j),new\rightarrow(i+1,j)(其他同理)

  3. (i,j)\rightarrow new,(i+1,j)\rightarrow new,new \xrightarrow{\text{同时选理科的额外快乐}}ED(其他同理)

每个点只能选择文科或理科,当某个点选择了文科,那么它向理科(ED)的边都应该要被断开。

它直接连向ED的边、它和别的点组合连向ED的边都要切断

这些边的权值就会从最终答案中减去

infinf同时选文科选理科选文科同时选理科infinf选理科选文科ST(i,j)ED(i+1,j)newnew'
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一定是我做题太少了

看不出这是个最小割

我们将每个人看成一个点,然后如下建边:

  1. 源点向每个人连流量为其总收益的边(\sum_{j=1}^n E_{i,j})

  2. 每个人向汇点连流量为其花费的边

  3. ij连流量为E_{i,j} \times 2的边

然后用所有能赚到的利润减去最小花费就可以了

第三条,如果两个人都选,可以获得E_{i,j}的利润

如果有一个不选,会亏损E_{i,j}的利润

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

和网络流24题中的骑士共存问题和[TJOI2013]攻击装置相似

不过不能直接把所有点拆成两种

我们还是可以借助思路

据说这又叫“网络流的最小路径覆盖”

为了使每个点指经过一次,我们把点拆成两个

从源点向每个点的入点连一条边权为1的边

从每个点的出点与汇点连一条边权为1的边

每个点的入点向能到达的点的出点连一条边权为1的边

然后拿可以放的节点数-最大流

据说还可以用按照有上下界网络流套路建图后求s到t的最小流做???

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

经典的最小路径覆盖问题

可以看出一开始有 1~n条路径(1~n)

每次可以挑选一个点,合并两条路径

但是一个点只能用一次

所以我们把点拆成两个

从源点向每个点的入点连一条边权为1的边

从每个点的出点与汇点连一条边权为1的边

每个点的入点向能到达的点的出点连一条边权为1的边

用 n-最大流 就是答案

至于输出:

突然有点尴尬

随便乱搞吧

用过的边就是合并过的

把这些边合并起来就可以得出路径

(搞个并茶几???)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

此题与网络流24题中的骑士共存问题一致

最大流=最小割

用点数-去可以攻击的最大匹配

可以使用网络流或二分图

1/1
Search
search