增广路是什么
算最大流时反复找的增广路,指的是【0】。
这张网每秒最多过多少水
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水: CAP = {0: {1: 6, 2: 5}, 1: {3: 4, 4: 2}, 2: {4: 5}, 3: {6: 3}, 4: {3: 2,
自己写:把一条增广路灌满
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水:找路那半已经写好了,b 是这条路上最细的一段。补上灌水这两步。 CAP = {0: {1: 6, 2: 5}, 1: {3: 4, 4: 2}, 2: {4: 5
⚠️ 把卡住它的那一刀找出来
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水:最大流跑完之后,残量图里从水源还走得到的点已经算进 side 了。把跨出 side 的那些边收成割,输出最大流/割容量/割上有几条边。
⚠️ 拆掉一根管子,有时候一点影响都没有
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水:把 4 → 3 那根管子整根拆掉,和原来的网各跑一次最大流,再数一数拆完还剩几条管子,三个数一起输出。
🔴 加粗哪根管子才真的有用
一张管道网,0 号是水源、6 号是出口,每条管子上的数字是每秒最多能过多少水:给你一次加粗的机会。分别试试加粗最细的那根(1 → 4,从 2 到 4)和加粗割上的那根(3 → 6,从 3 到 5),连同原始值一起输出三个数。 CAP = {
什么样的问题能套二分图匹配
下面这些里,天生就是二分图匹配的是【0】。
⚠️ 先到先得为什么不够
按名单顺序一个个来,每人挑一台还空着的机器。这么配的毛病是【0】。
最多能同时开几台
五个人、四台机器。每个人只会开其中几台,一台机器同时只能一个人用,一个人也只能占一台: PEOPLE = ['阿岚', '小满', '阿泰', '南风', '北辰
⚠️ 先到先得能配上几对
五个人、四台机器。每个人只会开其中几台,一台机器同时只能一个人用,一个人也只能占一台:这次按名单顺序来,每人挑第一台还空着的机器: PEOPLE = ['阿岚', '小满', '阿泰', &#