点数翻倍代价翻几倍
点数从 7 涨到 14,边数也跟着差不多翻倍。算一算拓扑排序在两种规模下各做多少次减法。 (本题用 g++ -std=c++17 -O0 编译。)
从一句人话认出算法
把选型写成一个函数:从需求描述里找关键词,认出该用哪一类算法。认不出来就老实说 再问一遍。 (本题用 g++ -std=c++17 -O0 编译。)
选之前先看图有没有环
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b。 选算法之前还有一步:先看这张图能不能排全。能就直接排,不能就得先缩点。两张图各判一次。 (本题用 g++ -std=c++17 -O0 编译。)
交付图算法先验什么
第 1 步:五条验收,一条一条过 第 2 步:第 1 条:数对上了 第 3 步:第 2 条:数对上了 第 4 步:第 3 条:数对上了 第 5 步:第 4 条:数对上了 第 6 步:第 5 条:数对上了 第 7 步:全过:可以交付 判环 分
答案不唯一时怎么验收
拓扑序不唯一、匹配方案不唯一、最大流的走法也不唯一。验收这类结果,靠的是【0】。
同一个函数有环时骗你
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b。 把分层函数在两张图上各跑一次:左边是那张 DAG,右边是加了 5 → 3 的那张。 运行下面这段程序: #include <algorithm> #includ
第一步:先判有没有环
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b。 交付流程的第一步:判环。两张图各判一次。 (本题用 g++ -std=c++17 -O0 编译。)
第二步:几轮做完备几台
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b。 第二步:算出并行要几轮,以及最宽的那一层有几个任务——那就是最多要备几台机器。 (本题用 g++ -std=c++17 -O0 编译。)
第三步:有环就缩点
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环。 第三步:既然判出有环,就把它缩成 DAG。补全 condense,输出缩完的点数和边数。 (本题用 g++ -std=c++17 -O0 编译。)
第四步:吞吐量和它的上界
一张管道网,0 号是水源、6 号是出口,cap[u][v] 是 u→v 这根管子每秒最多能过多少水。 第四步:算出这张网的最大流,再算出水源接出去的总容量,两个一起输出。 (本题用 g++ -std=c++17 -O0 编译。)