28 ms·
Sorry if I am missing something, but why not run max-flow? Max-flow is simple to implement; basically just DFS/BFS in a loop. Also, a more advanced variant with
by tylerhou 2y ago
Sorry if I am missing something, but why not run max-flow? Max-flow is simple to implement; basically just DFS/BFS in a loop. Also, a more advanced variant with better runtime, scaling max-flow, is not too much harder.
https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final.pdf https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final...
- ColinWright 2y agoUnless I'm missing something (which is entirely possible, I have a cold and might not be thinking straight) ... Max-Flow runs on directed graphs. These are undirected graphs.
- eutectic 2y agoAlso, the problem is to find a global min-cut, which requires all-pairs max flow.
- gloria_mundi 2y agoNot actually all-pairs max flow, you can fix the source and consider all possible sinks. In the AoC problem we also know that the min-cut is 3, so we can abort the flow algorithm as soon as we have found a 4-flow.
- armanboyaci 2y agoYou can compute the max-flow of an undirected graph. The edges have capacities and in the undirected case you assume that capacity can be used in both 'directions'.