演算法›Ch4 圖論演算法
第 77 題/共 111 題
◀ AL 77/111
77. Difference Constraints、Bellman-Ford、Constraint Graph
#AL-04-077中Difference ConstraintsBellman-FordConstraint Graph

(10%) Find the set of feasible solutions {x=(x1,x2,x3,x4,x5)}\{x = (x_1, x_2, x_3, x_4, x_5)\} or determine that no feasible solution exists for the following system of difference constraints:

x1−x3≤1x2−x3≤4x4−x5≤−2x3−x4≤4x5−x1≤3x4−x2≤−7x1−x2≤−2x5−x3≤1\begin{aligned} x_1 - x_3 &\le 1 \\ x_2 - x_3 &\le 4 \\ x_4 - x_5 &\le -2 \\ x_3 - x_4 &\le 4 \\ x_5 - x_1 &\le 3 \\ x_4 - x_2 &\le -7 \\ x_1 - x_2 &\le -2 \\ x_5 - x_3 &\le 1 \end{aligned}
📄 成大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法
本章題號 · 61–80 / 111