Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Solution: mincut
- 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.
- We aim to minimize the negative of productivity.
- Edges:
- among all pairs of nodes i,j within same layer, edge of capacity D[i][j] from j to i.
- Edge from source to all nodes of layer 1, with capacity MAX-P[i][1].
- Edge from all nodes of layer 1 to source, with capacity INF.
- Edge from all nodes in layer M to sink , with capacity INF.
- Edge from all nodes in layer (j-1) to corresponding nodes in layer j with capacity P[i][j] for 2<=j<=M
- Edge from all nodes in layer j to corresponding nodes in layer (j-1) with capacity INF for 2<=j<=M
- where MAX = maximum possible value of P[i][j]
- ans = maxflow - N*MAX
Add Comment
Please, Sign In to add comment