Transportation Delegation
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 is a classical max flow problem.
- First row of nodes on the left represent factories. Supernode proves them each with a flow of 1.
- next set of nodes represent shippers. We have to encode the fact that they can only pick up from one factory, though. This is done by having an "in" node and an "out" node. The in node receives from all potential factories, and the flow between the in node and out node is at max 1. We'll get to what happens once we pass the out-nodes in a second.
- The right hand side is mirrored, with factories sinking at most 1 to the supernode sink, and rows for the suppliers guaranteeing that we only deliver to a single factory.
In the middle of the graph, we can connect any nodes which can transmit flow from one to another. If two shippers share a common state, they are able to send infinite flow to that shipper. Draw edges from the out-nodes of the supply side to the in-nodes on the factory side. Runtime is ve^3, and E ~= V here, so we're looking at V^3, which is borderline.
We can significantly optimize this, though. Any node that is in an infinite cycle can be combined in the same node. This means that the middle part of the graph with all our crazy edges reduces to one node for each strongly-connected-component of states (i.e. any pair of states that have a transportation company, or set of transportation companies that can transport between them are in the same SCC). Note that any shipper will be connected to exactly 1 SCC.
Our NEW graph boils down to:
- "supplier" nodes
- shipping in nodes
- connected to any factory which is in a state served by that shipper
- state SCC nodes
- connected with weight 1 to any shipper in-node which serves that SCC
- shipping out nodes
- connected with weight 1 to the SCC which serves that shipper
- factory nodes
This brings the complexity of the graph down enough that it should run fast enough.