青竹qingzhu

网络流

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 题解(7)

/ 注册

全部文章 / 网络流（共10篇）

2020牛客暑期多校训练营（第一场）H 网络流边权改变

题意 n个点m条边的有向图，给出边的单位流量费用，q次询问，每次询问有有u,v两个整数，表示所有边的容量为u/v，对于每次询问，输出从1到n流量为1时的最小费用，流量达不到1时，输出“NaN”. 题解每条边的容量是相同的，如果边的容量为1的时候流量为maxflow，那么边的容量为u/v时，流量就是...

2020-07-17

0 581

#6005. 「网络流 24 题」最长递增子序列

#6005 题意给定正整数序列x1 , … , xn 。（1）计算其最长递增子序列的长度s。（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（每个数只能取一次）（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。思路第一问：n...

2020-07-13

0 533

P1231 教辅的组成——网络流为什么要拆点

洛谷P1231 参考博客大佬Siyuan 题意有n1本书，n2本练习册，n3本答案。给出m1个书和练习册的联系，m2个书和答案的联系，一本书一本练习册一本答案为一册，问最多可以组成多少册。思路如果只有两样东西就是典型的最大二分匹配问题，但这里有三种，所以匈牙利算法做不了，可以用最大流。建图方法...

2020-07-13

0 403

#6010. 「网络流 24 题」数字梯形最大费用最大流建图

题目链接题意分别求三个规则满足条件的所有路径最大和。思路网络流问题最重要的是建图问题。 1.路径互不相交，也就是一个数字只能用一次，那就是拆点了，每个点拆分为入点和出点，入点和出点之间连一条容量为1费用为权值的边；建立一个源点和一个汇点，源点与第一行的入点相连，容量为1费用为0，最后一行的...

2020-07-13

0 584

#6014. 「网络流 24 题」最长 k 可重区间集

题目链接题意给n个区间的集合S，求一个区间集合A属于S，且集合A的每个区间的长度和最大，每个点最多可以选k次。思路首先每个点可以重复k次，可以用流量来限制，用最大费用最大流来做。将所有区间离散化，源点在最左边，汇点在最右边，每一个点都向右边相邻的点连一条容量为INF，费用为0的边，对于每个...

2020-07-13

0 622

#6121. 「网络流 24 题」孤岛营救问题迷宫分层图

题目链接题意一个有n*m个方格的迷宫，相邻的方格之间可能是墙，也可能是连通的，也可能是门，门有多种类型，需要对应类型的钥匙才可以通过，某些方格里存放着钥匙，问从左上角（1,1）到（n,m）最短的时间。思路分层图，以携带的钥匙为层数，用二进制法存，按题意建图后跑spfa。 #include ...

2020-07-13

0 485

#6122. 「网络流 24 题」航空路线问题输出路径

题目链接题意一张航空图，从西向东，1-n个城市，城市之间有若干条航线，航线可以往返，求从1到n再从n到1最多经过多少个不同的城市，1和n可以经过两次，其他城市都只能经过一次。思路经过次数，显然要想到拆点和流量控制，将每个城市点拆成入点和出点i和i+n，1与1+n之间的容量是2，费用是0，n与...

2020-07-13

0 509

#6224. 「网络流 24 题」深海机器人问题收益记一次可走多次

题目链接题意 P*Q的网格中，给出每条边的收益，若干个机器人的起始位置和目的地。机器人只能往东或北走，每条边可以走多次，但只能算一次收益，求最优机器人移动方案下的最大收益。思路有机器人数量，边的收益，这种问题显然优先考虑最大费用最大流。一条边的收益只能记一次，连一条容量为1费用为权值的边；然后...

2020-07-13

0 510

#6227. 「网络流 24 题」最长 k 可重线段集问题

题目链接题意 x0y平面上n条开线段，求一个线段子集，使得它的线段长度和最长，且对于每条垂直于x轴的线段都不超过k条线段与之相交。思路类似最长k可重区间集问题，因为只对x轴上的点有限制，一样的，离散化后建边，跑最大费用最大流，需要注意的是这里是开线段，有个神奇的处理就是把l改为l * 2+1，...

2020-07-13

0 496

牛客练习赛65 E 网络流点权改变的处理方法

题目链接题意 n点m条边的无向图，每个点的点权是ai，没经过一次点，点权增加bi，即第k次经过i点权值为ai + (k - 1) * bi，现给出q个xi和q个yi，每次从中选出一组xi,yi，统计从xi到yi的代价和（代价为从xi到yi经过的所有点的点权和），每个点只能选一次，q次后（也就是全选...

2020-07-13

0 417