Wednesday, October 14, 2009

[SPOJ] MOBIVINA

This problem is a straight application of the maximum flow / minimum cut algorithm.

Construct a graph that has N+2 vertices.
N vertices corresponding to N people. 1 corresponds to Mobi, 1 corresponds to Vina.

Person i - Person j: capacity C[i,j]
Mobi - Person i : capacity M[i]
Person i - Vina: capacity V[i]

A cut Mobi-Vina corresponds to a way to assign people to services.
Cut's capacity = cost
Thus, maximum flow <=> minimum cut.

1 comment: