GST - Editorial

editorial
gst
hard
may10

#1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

Approach Taken:

This can be solved via network flow. First, say we have already verified the trivial condition that the total fraction is |V|-1. For the moment, fix two nodes u and v. Construct the following directed graph H on node set V. Use the following notation. For a node a let f(a) denote the total fraction assigned to edges having a as an endpoint. For a set S let f(S) denote the total fraction assigned to edges having both endpoints in S. Finally, for a set S let f*(S) denote the total fraction assigned of edges having exactly one endpoint in S.

  1. For each edge (a,b) of the original graph with value f(a,b) add two opposing directed arcs each with capacity f(a,b)/2
  2. For each node a in V{u,v}, add a directed arc from a to v with capacity 1
  3. For each node a in V{u}, add a directed arc from u to a with capacity equal to f(a)/2

The claim is that there is a violated set S with u in S and v not in S if and only if the maximum flow from u to v in the graph H described above is strictly less than |V|-1. For one direction, say S is a violated set containing u but not v. Let’s examine the capacity of the corresponding cut S in H:

  • |S|-1 total capacity is from edges created in step 2 (1 from each node except u)
  • f * (S)/2 total capacity is from edges created in step 1
  • (f(a _ 1) + f(a _ 2) + … + f(a _ k))/2 total capacity is from edges created in step 3 where a _ 1, …, a _ k are the nodes not in S

Now, f(a _ 1) + f(a _ 2) + … + f(a _ k) = 2f(V) - f(s _ 1) - f(s _ 2) - … - f(s _ |S|) where the s _ i are the nodes in S (each edge contributes to two vertices). Therefore, the total capacity of the cut is:

|S| - 1 + f * (S)/2 + f(V) - f(a _ 1)/2 - f(a _ 2)/2 - … - f(a _ k)/2

Now, each edge with exactly one endpoint in S has half its value counted among f*(S)/2 and half its value counted among the f(a _ i)/2. Each edge with both endpoints in S is counted twice among the f(a _ i)/2. Therefore, f * (S)/2 - f(a _ 1)/2 - f(a _ 2)/2 - … - f(a _ k)/2 = f(S). Thus, the capacity of the cut is:

|S| - 1 + f(V) - f(S) = |S| - 1 + |V| - 1 - f(S)

Under the assumption f(S) > |S|-1, we have the cut capacity being strictly less than |V|-1. Therefore, by the max-flow/min-cut theorem the maximum flow between u and v is less than |V|-1.

On the other hand, if the maximum flow between u and v is less than |V|-1 then consider a cut S containing u with capacity less than |V|-1. The arguments made above can be easily reversed to yield a non-trivial set S with f(S) > |V|-1.

So, if we know two nodes u and v such that u is in a violated set S and v is not, then we can recover such a set using the flow-based algorithm mentioned above. Fix a node u and try all |V|-1 other nodes v. We know that either u is in S or u is not in S so for some guess v we have u is in S and v is not, or vice-versa. So, we just need to run the above algorithm at most 2|V|-2 times: once from u to each node v and once from each node v to u.

While converting to doubles would probably not cause any rounding errors in any reasonable implementation, the bound on the denominators of the rational numbers was chosen such that a careful implementation of rational numbers and either the Edmonds-Karp or Dinic’s flow algorithm would not result in overflow if 64 bit integers were used.