Transportation Delegation: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "This problem asks us how to supply factories with a network of "shipping" connections where there are restrictions that each shipper only sources from one company, and deliver..." |
imported>Kmk21 No edit summary |
||
| Line 1: | Line 1: | ||
This problem asks us how to supply factories with a network of "shipping" connections where there are restrictions that each shipper only sources from one company, and delivers to one company. | This problem asks us how to supply factories with a network of "shipping" connections where there are restrictions that each shipper only sources from one company, and delivers to one company, and each company supplies at most one factory. | ||
From these constraints, we can deduce the restriction that each shipper will only ever ship a single package from one place to another, though not explicitly disallowed, there is no situation where it would be optimal for the shipper to pick up a second package somewhere else (delivered from another shipper). | |||
Proof: Suppose a shipper were to deliver from one supplier to one factory, but on another part of its route, pick up a package in a third party state and drop it off in another third party state. By the first restriction in the description, this would imply that the second package would have been produced by the same supplier as we already picked up from. This would imply that supplier was providing goods for a second factory, violating the third constraint. Therefore each shipper can only move a single "box" from one place to another. | |||
This is a classical max flow problem. | This is a classical max flow problem. | ||
* First row of nodes on the left represent factories. Supernode proves them each with a flow of 1. | * First row of nodes on the left represent factories. Supernode proves them each with a flow of 1. | ||
* | * Each "shipper" has an in node and an out node limiting the flow across that shipper to 1. | ||
* The right hand side is mirrored, with factories sinking at most 1 to the supernode sink | * The right hand side is mirrored, with factories sinking at most 1 to the supernode sink. | ||
* Edges are drawn from the out-node of each supplier to in nodes of any other shipper that we share a state with, or to factories in those states | |||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
| Line 30: | Line 17: | ||
[[Category:Implementation Medium]] | [[Category:Implementation Medium]] | ||
[[Category:Max Flow]] | [[Category:Max Flow]] | ||
[[Category:In-Out Nodes]] | [[Category:In-Out Nodes]] | ||
Latest revision as of 23:16, 9 November 2017
This problem asks us how to supply factories with a network of "shipping" connections where there are restrictions that each shipper only sources from one company, and delivers to one company, and each company supplies at most one factory.
From these constraints, we can deduce the restriction that each shipper will only ever ship a single package from one place to another, though not explicitly disallowed, there is no situation where it would be optimal for the shipper to pick up a second package somewhere else (delivered from another shipper).
Proof: Suppose a shipper were to deliver from one supplier to one factory, but on another part of its route, pick up a package in a third party state and drop it off in another third party state. By the first restriction in the description, this would imply that the second package would have been produced by the same supplier as we already picked up from. This would imply that supplier was providing goods for a second factory, violating the third constraint. Therefore each shipper can only move a single "box" from one place to another.
This is a classical max flow problem.
- First row of nodes on the left represent factories. Supernode proves them each with a flow of 1.
- Each "shipper" has an in node and an out node limiting the flow across that shipper to 1.
- The right hand side is mirrored, with factories sinking at most 1 to the supernode sink.
- Edges are drawn from the out-node of each supplier to in nodes of any other shipper that we share a state with, or to factories in those states