# 1. Revenge of the Leptons

Construct a directed graph with nodes s, t, and x_{ij} for i=1..n and j=1..m. Create an edge with weight c_{i1} from s to each node x_{i1} and of weight +∞ from each node x_{im} to t. Create an edge with weight c_{i j+1} from each node x_{ij} to x_{i j+1} and an edge of weight s_{ij} from each node x_{ij} to each node x_{i+1 j} (treating n+1 as 1). Now find a minimum s-t cut on this graph, and set t_{i} to be the minimum j for which x_{ij} is on the t side of the cut.

Clearly this takes polynomial time. Does it work? The set S of nodes on the s side of the cut corresponds to bays that have not been cleaned out yet, while the set T of nodes on the t side correspond to those that have. The cost of the cut is the sum of

c

_{ij}for each i and j = t_{i}, to pay for the edge between x_{i-1 j}and x_{ij}, pluss

_{ij}for each i and each j for which x_{ij}is in S and x_{i+1 j}is not; this corresponds to the cost of maintaining the force-field.

Since this is exactly the cost of the objective function in the problem, by minimizing it we minimize our cleaning cost.

# 2. A tripartite marriage problem

We'll have a variable yS for each triple S on the list, that is 1 if the triple is married and 0 otherwise. The linear program is