Guest User

Untitled

a guest
Sep 27th, 2016
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.75 KB | None | 0 0
  1. Solution: mincut
  2.  
  3. M+2 layers:
  4.  
  5. 0th and (M+1)th layer for source and sink, M other layers for each role in firm, each containing N nodes.
  6.  
  7. We aim to minimize the negative of productivity.
  8.  
  9. Edges:
  10.  
  11. among all pairs of nodes i,j within same layer, edge of capacity D[i][j] from j to i.
  12.  
  13. Edge from source to all nodes of layer 1, with capacity MAX-P[i][1].
  14. Edge from all nodes of layer 1 to source, with capacity INF.
  15. Edge from all nodes in layer M to sink , with capacity INF.
  16.  
  17. Edge from all nodes in layer (j-1) to corresponding nodes in layer j with capacity P[i][j] for 2<=j<=M
  18. Edge from all nodes in layer j to corresponding nodes in layer (j-1) with capacity INF for 2<=j<=M
  19.  
  20. where MAX = maximum possible value of P[i][j]
  21.  
  22. ans = maxflow - N*MAX
Add Comment
Please, Sign In to add comment