⚠️ 选之前先看图有没有环
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b:选算法之前还有一步:先看这张图能不能排全。能就直接排,不能就得先缩点。两张图各判一次。
交付一个图算法的解,要验哪几样
写完一个图算法就交付,最该先验的是【0】。
⚠️ 答案不唯一时拿什么当验收标准
拓扑序不唯一、匹配方案不唯一、最大流的走法也不唯一。验收这类结果,靠的是【0】。
⚠️ 同一个函数,有环的图上会骗你
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b:把分层函数在两张图上各跑一次:左边是那张 DAG,右边是加了 5 → 3 的那张。 DEP = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)
第一步:先判有没有环
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b:交付流程的第一步:判环。两张图各判一次。
第二步:几轮能做完,最多要几台机器
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b:第二步:算出并行要几轮,以及最宽的那一层有几个任务——那就是最多要备几台机器。
第三步:有环就缩点
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:第三步:既然判出有环,就把它缩成 DAG。输出缩完的点数和边数。
第四步:吞吐量和它的上界
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水:第四步:算出这张网的最大流,再算出水源接出去的总容量,两个一起输出。 CAP = {0: {1: 6, 2: 5}, 1: {3: 4, 4: 2}, 2: {4
交付:五条验收条款一起过
七个构建任务编号 0~6,(a, b) 表示 a 做完才能做 b:最后一步:把五条验收条款补全,一次全部验过。每一条都落在一个唯一的数上——顺序可以不同,但这些数不能不同。
「查找」和「匹配」要回答的事差在哪
一小段,在长带子上找落点 文本 模式 在一排数字里找出 42 在第几个,和在一段文字里找出某个词出现在哪儿——后一件事和前一件的区别是【0】。