有源汇有上下界的最小流(LOJ117)
时间: 2024-02-01 08:02:52 浏览: 190
这是一个IT类问题。该问题可以使用网络流算法解决。首先用 Dinic 或 ISAP 算法求出最大流,然后根据最大流的值和边的上下界,构造一个新图,使得原图中的每条边都对应着新图中的一些流量限制。具体地,对于一条容量为$c$,下界为$l$,上界为$u$的边$(u,v)$,我们在新图中从$u$向$v$连一条容量为$u-l$的边和一条容量为$u-l$,费用为$c$的边,再从源点向$u$连一条容量为$l$的边,费用为$0$,最后从$v$向汇点连一条容量为$l$的边,费用为$0$。在新图上跑一遍费用流,如果总流量等于原图的最大流,则新图中的最小费用即为所求最小流,否则原图不存在满足上下界的流。
相关问题
LOJ-6279-数列分块入门3(分块, 二分)
题目描述
给定一个长度为n的序列a,有m次询问。每次询问给定l, r, k,要求区间[l, r]中第k小的数。
输入格式
第一行两个整数n,m。 接下来一行n个整数,表示序列a。 接下来m行,每行三个整数l,r,k。
输出格式
对于每个询问,输出一行一个数,表示区间[l, r]中第k小的数。
输入样例
5 3
1 3 2 4 5
1 5 2
2 4 1
3 5 3
输出样例
2
3
5
算法1
(分块) $O(n\sqrt n)$
我们可以预处理出每一个块的信息,每个块又分为若干小块,每个小块中的数都小于等于块中的最大值,可以用二分查找确定小块中满足条件的数的个数,然后用根号分治处理。
时间复杂度
每次查询的时间复杂度是 $O(\sqrt n\log n)$ 的,总时间复杂度是 $O(n\sqrt n\log n)$ 的。
参考文献
算法竞赛进阶指南
C++ 代码
算法2
(二分答案) $O(n\log^2n)$
我们二分答案,然后统计序列中小于等于这个答案的数的个数,统计方法可以用归并排序,在时间复杂度 $O(n\log n)$ 的时间内完成。
时间复杂度
每次查询的时间复杂度是 $O(n\log^2n)$ 的,总时间复杂度是 $O(mn\log^2n)$ 的。
参考文献
算法竞赛进阶指南
C++ 代码
LOJ6354 & 洛谷4366:[Code+#4]最短路——题解
这道题需要使用 Dijkstra 算法来解决。
Dijkstra 算法是一种贪心算法,用于解决没有负权边的单源最短路径问题。算法的基本思想是:从源点开始,每次选择当前最短路径的节点,并更新其周围节点的距离。
具体步骤如下:
1. 初始化距离数组 dist,将源点到自己的距离设为 0,其他点到源点的距离设为无穷大。
2. 创建一个集合 visited,用于存储已经确定最短路径的节点。
3. 将源点加入 visited 集合中。
4. 对于源点周围的每个节点,更新它们到源点的距离。如果距离更短,则更新 dist 数组。
5. 从 dist 数组中选择距离最短的节点,将其加入 visited 集合中。
6. 重复第 4 步和第 5 步,直到所有节点都被加入 visited 集合中。
7. dist 数组中的值即为源点到每个节点的最短距离。
注意事项:
1. Dijkstra 算法只适用于没有负权边的图。
2. Dijkstra 算法不能处理有向无环图中的负权边。
下面是 Python 代码实现:
阅读全文
相关推荐







