PROBLEM LINK:Author: Vaibhav Gosain Editorialist: Vaibhav Gosain DIFFICULTY:HARD PREREQUISITES:maxflow, min cut: Topcoder Tutorial EXPLANATION:This problem can be solved via the concept of minimum cut. We model the following graph, containing M+2 layers: 0th and (M+1)th layer for source and sink, M other layers for each role in firm, each containing N nodes. Edges:
where MAX = maximum possible value of P[i][j] The required maximum productivity of the firm = N*MAX  mincut Why does this work? Let S be the source and T be the sink. The infinite edge from layer j to layer j1 ensures that if ith node in layer j is on the S side in the cut, corresponding node in layer j1 will also be on the S side in the cut. Now, say the last layer whose ith node lies in S side of the cut is R[i]. We claim N*MAX  (cut of above graph) is the value of total productivity of the firm if person i is given role R[i] for all i. Reason:
AUTHOR'S SOLUTION:Author's solution can be found here. asked 03 Oct '16, 22:11
