https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

https://www.bilibili.com/video/BV1wK411g7ck

#### 2. A cohort of spies

• 顶点：起点$s$，间谍的出发城市$\cup \{s_i\}$，安全城市$T$，终点$t$
• 边：分为三部分
• 起点：$(s ,s_i)$
• 逃生路径：$(s_i,t_j)$
• 终点：$(t_i,t), t_i \in T$
• 容量：
• 起点：$c(s, s_i)=c$
• 逃生路径：$c(s_i,t_j)=c$
• 终点：$c(t_i,t)=c$（这样可以保证不会有超过$c$个人通过每个安全城市）

#### 3. Max Flow, Min Cut, and Duality

##### (a)

• $x_1:(S,A)$
• $x_2:(S,B)$
• $x_3:(A,T)$
• $x_4:(A,B)$
• $x_5:(B,T)$

#### 4. Zero-Sum Battle

##### 1

Status: Infeasible
x1 = 0.42647059
x2 = 0.48529412
x3 = 0.088235294
z = 0.0
##### 2

Status: Optimal
y1 = 0.34117647
y2 = 0.30588235
y3 = 0.35294118
z = 0.0

from pulp import *

## trainer A
probA = LpProblem("TrainerA", LpMaximize)

x1 = LpVariable("x1", 0, None)
x2 = LpVariable("x2", 0, None)
x3 = LpVariable("x3", 0, None)
z = LpVariable("z", 0, None)

probA += z
probA += z <= -10 * x1 + 4 * x2 + 6 * x3
probA += z <= 3 * x1 - x2 - 9 * x3
probA += z <= 3 * x1 - 3 * x2 + 2 * x3
probA += x1 + x2 + x3 == 1
probA.solve()

print("Status:", LpStatus[probA.status])
for v in probA.variables():
print(v.name, "=", v.varValue)

# trainer B
probB = LpProblem("TrainerB", LpMinimize)

y1 = LpVariable("y1", 0, None)
y2 = LpVariable("y2", 0, None)
y3 = LpVariable("y3", 0, None)

probB += z
probB += z >= -10 * y1 + 3 * y2 + 3 * y3
probB += z >= 4 * y1 - y2 - 3 * y3
probB += z >= 6 * y1 - 9 * y2 + 2 * y3
probB += y1 + y2 + y3 == 1
probB.solve()

print("Status:", LpStatus[probB.status])
for v in probB.variables():
print(v.name, "=", v.varValue)

#### 5. Minimum Spanning Trees

##### (a)

• $x_{u,v}=1$表示选择这条边，否则表示不选；
• 约束条件1的含义是，对于任意一个划分，至少选择一个割边；
• 约束条件2的含义是，边的数量小于等于$|V|-1$

##### (b)
• 约束1：$2^{|V|}$
• 约束2：$1$
• 约束3：$|E|$

##### (c)

a  b
c  d

(a, b) : 1
(b, c) : 2
(c, d) : 100
(d, a) : 1
(a, c) : 1
(b, d) : 0.5

MST为$(a, b),(a,c),(a,d)$，权重和为$3$。