Splitting Every Hall

Evacuation planning. Twenty halls, forty two-way corridors. Corridor c moves at most cap(c) people per minute, and hall v also has a limit c(v) on how many people per minute can pass through it, because of floor area.

You want maximum throughput from the entrance hall to the exit hall. Edge capacities alone cannot express a hall limit: three corridors each capped at c(v) still deliver 3 * c(v) into v. What network do you build?

Run max flow with corridor capacities only, then scale flow down through any hall that exceeds its limit until every constraint holds.

Split each hall v into v_in and v_out joined by a single edge of capacity c(v). Rewrite every corridor between u and v as u_out → v_in and v_out → u_in at the corridor capacity. Run max flow from entrance_out to exit_in.

Give every corridor entering v capacity min(cap(corridor), c(v)), leaving one vertex per hall.

Add a self-loop at v of capacity c(v).