求如图所示网络的最大流，弧边的数字是（容量，成本）。
求如图所示网络的最大流，弧边的数字是（容量，成本）。
参考答案和解析
图5-11中已有一个值为4的可行流。先用标号法找增广链：s标号：(0，+∞)；1标号：(s，4)；2标号：(-1，1)；3标号：(-2，1)；t标号：(3，1)。 反向追踪得增广链：P={s，(s，1)，1，(2，1)，2，(3，2)，3，(3，t)，t}，θ=1，调整后得图5-12，可行流的值为5。 再找增广链：s标号：(0，+∞)；1标号：(s，3)。s已检查，再检查点1，后向弧(2，1)上f(2，1)=0，前向弧(1，3)上f(1，3)=b(1，3)=2，标号进行不下去，故已得最大流，其流值为5。 对应最小截集(W， )，W={s，1}， ={2，3，4，t}。其截集容量为：C(W， )=b(s，2)+b(1，3)=3+2=5。 说明：Ford-Fulkerson方法是有缺点的。曾有人举出一个例子，当网络的容量是无理数时，用Ford-Fulkerson方法可能找不到最大流。1972年Edmonds和Karp提出了一种改进方法，克服了上述缺点。
相关考题：
在两组结构面与边坡的赤平极射投影图上（如图所示），最不稳定的边坡是：A.两组结构面的交点M在边坡投影弧的对侧，如图a)所示B.两组结构面的交点M在边坡投影弧的内侧，如图b)所示C.两组结构面的交点M在边坡投影弧的外侧，但两组结构面的交线在边坡上没有出露，如图c)所示D.两组结构面的交点M在边坡投影弧的外侧，而两组结构面的交线在边坡上有出露，如图d)所示
下列选项属于最小费用流问题的假设是（）A、至少一个供应点和一个需求点，剩下都是转运点B、通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量C、网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点且在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比D、最小费用流问题的目标在满足给定需求条件下，使得通过网络供应的总成本最小（或总利润最大）
关于最大流量问题，以下叙述（）正确。A、一个容量网络的最大流是唯一确定的B、达到最大流的方案是唯一的C、当用标号法求最大流时，可能得到不同的最大流方案D、当最大流方案不唯一时，得到的最大流量亦可能不相同
单选题关于最大流量问题，以下叙述（）正确。A一个容量网络的最大流是唯一确定的B达到最大流的方案是唯一的C当用标号法求最大流时，可能得到不同的最大流方案D当最大流方案不唯一时，得到的最大流量亦可能不相同