We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
C++ solution, passes all test cases. Same algorithm as most of the other top-voted comments in this thread: Constructs bipartite graph with source, sink, and two regions, which we can call A and B, each with N nodes (the number in the original crab graph), then uses Ford-Fulkerson to find the max flow (with BFS to find paths in the residual network) as described in Chapter 26.2 of CLRS introduction to algorithms. Each edge in the original crab graph corresponds to two symmetric edges between A and B, and has capacity 1. Also, every node in region B has a capacity 1 edge to the sink. Finally, the source has an edge of capacity min(T, degree(a)) to each node in region a, where T is the max number of legs a crab can have, and degree(a) is the number of edges coming out of node a into region B.
At first, it seems non-obvious why max flow is equivalent to the number of nodes covered by crabs, but if you think about it for a while, it makes sense: because each b in region B has a capacity 1 edge going to the sink, that means each b can have at most 1 nonzero flow edge going into it from region A; in other words, each node can belong to at most one crab. Additionally, setting the source to a capacities to min(T, degree(a)) limits the number of legs each crab has to T. Hence, the flow into the crab head nodes in region A is the same as the number of leg nodes in the optimal crab graph. Finally, the number of heads are also included, since there are also head nodes in region B, which will receive 1 flow from one of its legs in region A. Hence, the max flow of this setup is exactly equal to the number of nodes covered by the optimal crab graph.
Crab Graphs
You are viewing a single comment's thread. Return to all comments →
C++ solution, passes all test cases. Same algorithm as most of the other top-voted comments in this thread: Constructs bipartite graph with source, sink, and two regions, which we can call A and B, each with N nodes (the number in the original crab graph), then uses Ford-Fulkerson to find the max flow (with BFS to find paths in the residual network) as described in Chapter 26.2 of CLRS introduction to algorithms. Each edge in the original crab graph corresponds to two symmetric edges between A and B, and has capacity 1. Also, every node in region B has a capacity 1 edge to the sink. Finally, the source has an edge of capacity min(T, degree(a)) to each node in region a, where T is the max number of legs a crab can have, and degree(a) is the number of edges coming out of node a into region B.
At first, it seems non-obvious why max flow is equivalent to the number of nodes covered by crabs, but if you think about it for a while, it makes sense: because each b in region B has a capacity 1 edge going to the sink, that means each b can have at most 1 nonzero flow edge going into it from region A; in other words, each node can belong to at most one crab. Additionally, setting the source to a capacities to min(T, degree(a)) limits the number of legs each crab has to T. Hence, the flow into the crab head nodes in region A is the same as the number of leg nodes in the optimal crab graph. Finally, the number of heads are also included, since there are also head nodes in region B, which will receive 1 flow from one of its legs in region A. Hence, the max flow of this setup is exactly equal to the number of nodes covered by the optimal crab graph.