最近版面活跃，来问个问题：
CLRS 26-3 Space shuttle experiments
Professor Spock is consulting for NASA, which is planning a series of space shuttle flights and must decide which commercial experiments to perform and which instruments to have on board each flight. For each flight, NASA considers a set E = {E1, E2, . . . ,Em} of experiments, and the commercial sponsor of experiment Ej has agreed to pay NASA pj dollars for the results of the experiment. The experiments use a set I = {I1, I2, . . . ,In} of instruments; each experiment Ej requires all the instruments in a subset Rj ⊆ I. The cost of carrying instrument Ik is ck dollars. The professor's job is to find an efficient algorithm to determine which experiments to perform and which instruments to carry for a given flight in order to maximize the net revenue, which is the total income from experiments performed minus the total cost of all instruments carried.

Consider the following network G. The network contains a source vertex s, vertices I1, I2, . . . ,In, vertices E1, E2, . . . ,Em, and a sink vertex t. For k = 1, 2. . . ,n, there is an edge (s, Ik) of capacity ck, and for j = 1, 2,. . . ,m, there is an edge (Ej, t) of capacity pj. For k = 1, 2, . . . ,n and j = 1, 2, . . . ,m, if Ik ∈ Rj , then there is an edge (Ik, Ej) of infinite capacity.

a.Show that if Ej ∈ T for a finite-capacity cut (S, T) of G, then Ik ∈ T for each Ik ∈ Rj.

b.Show how to determine the maximum net revenue from the capacity of the minimum cut of G and the given pj values.

c.Give an efficient algorithm to determine which experiments to perform and which instruments to carry. Analyze the running time of your algorithm in terms of m, n, and .

小问b我觉得是pj values减去minimum cut of G，也就是maximum flow of G，这是一个可行解，但我不知道怎么证明它是收益最大的解。

__________________
Critics are like eunuchs in a harem; they know how it's done, they've seen it done every day, but they're unable to do it themselves.

你的想法没错，证明的话可以指出这个问题的任意一个可行解，对应于图中的一个 S-T 割 C ，且这个可行解的收益为 \sum_{j=1}^k{p_j} - weight(C) 就好了。

一直在考虑如何用最大流表示收益，完全没想到把收益和cut的值对应起来..
换种思路就简单多了，我果然还是死脑筋，sigh