Hello, and welcome. My name is William. Today we're going to look at how to use network flow to actually solve a useful problem. The problem we're going to tackle is what I call the nice and owls problem, which is a slightly harder variation of another competitive programming problem, which I'll link in the description. I love this problem because of its simple and elegant solution, but also it's realistic real world application. Let's have a look.

Suppose there are n mice out on the field and there's a hungry owl about to make a move as soon as the owl can reach every single one of these mice. Further suppose that there are h holes scattered across the ground, and that each hole has a certain capacity for the number of mice that can help In it, we also happen to know that every mouse is capable of running a distance of are in any direction before being caught by the owl. The question asks, what is the maximum number of mice they can hide safely before being caught. If you only give this problem a try, now's a good time to pause the video and try and write some code. The first step is to figure out which holes each mouse can reach. visualize this by drawing a radius of our around each maps, and inside the radius there's a hole or the circle touches a hole will assume that the mouse can make it hole safely.

So if we draw an edge between a mouse and a hole, if the mouse can make it to that hole, we get the following graph. The next step is to actually match mice to holes to maximize the overall safety of the group by doing a simple quick inspection It's clear that not every mouse should be matched to any hole. For example, this orange mouse should probably not try and run to the hole with a capacity of three, because it's the only mouse that can reach the hole behind it with a capacity of one, making any bad decision like this has the chance to jeopardize the maximum number of overall mice, they can hide safely. The key realization with this problem is that the graph is actually bipartite. And once we know that, it actually becomes a much simpler problem because we can set up a flow graph and run a maximum flow algorithm to maximize the overall number of mice which can hide safely.

Here are the steps I would do to setup the flow graph and run a max flow. First I would create m mice nodes labeled zero through m minus one inclusive. Then on the other side, I would create h nodes Each representing a whole, I would label or index these nodes from m to m plus h minus one inclusive to give them a different ID than the mouse nodes, then I would place an edge with a capacity of one between the mouse and the hole. If the mouse can reach that particular hole in time, after that, I would connect an edge with the capacity of one from the source to each mouse to indicate that each node can have at most one mouse. And lastly, connect an edge from each hole node to the sync node with the capacity of the hole. The problem has now been transformed into a maximum flow problem, we can run any maximum flow algorithm to get the maximum number of mice that can be safe.

This is really neat, and it's worth looking at some source code to really understand how this setup works. All right, here we are in the source code. I've laid out some instructions on the top here in case you wanted to Download the code and actually play around with it on your machine. This program also uses the Ford Fulkerson flow solver we saw two videos ago. So I highly recommend you go and watch that video before continuing. I'll link to it in the description below, just in case you haven't seen it.

So let's get started. The first thing I do here is I create a mouse class, which is essentially a wrapper around a point object. Effectively, a mouse is just the point on a plane. I also do the same thing with the whole class, except that the whole class with addition to having a 2d point object it also has a certain capacity because we know that holes can only contain a certain number of mice. Next up in the main method, I create a bunch of mouse objects and place them in an array. I scour the mice more or less randomly across the field and then I do the same thing with holes.

The last thing I do in the main method is called the solve method which actually takes as input the two arrays we just created and a radius. The radius is how far a mouse can run from its current position before being caught by the hour. The sole method is where things really start to get interesting. Let's define some constants that will make our lives a lot easier. First is M which is just the number of mice that is each the number of holes we have following that I compute and the number of nodes which is the number of mice plus the number of holes plus to the plus two is to account for the source and the sink node. And as per convention, I always index SMT, the source and the sink two indices and minus one and minus two to ensure that they are unique.

After that I initialize the network flow solver base by providing And SMT the solver classes defined below. It's the exact same one from the Ford Fulkerson source code video. In short, the solver lets you add edges with various capacities to the flow graph and then find the max flow. Once it's all set up. The goal of this video is not to explain to you how the max flow itself is found, or how the solver works. I already discussed that previously.

What I really want to focus on in this video is how to set up the flow graph for this problem and push some flow through it when the graph is bipartite. Like it is in this problem, the setup is actually pretty straightforward. The first step is to hook up edges from the source s to each mouse with a capacity of one. Intuitively, this limits each mouse node to represent at most one mouse. This is necessary because we don't want a mouse node to represent more than one mouse that doesn't really make sense. The next part is to hook up mouse nodes with hole nodes in the flow graph, this is the middle section of the flow graph where we add an edge between a mouse node and the hole if the distance from a mouse to the hole is less than the radius.

In other words, if a mouse can make it to the hole on time, add an edge connecting the mouse and the hole. The last step is also important, you need to remember to hook up the edges between the holes and the sink. These edges are slightly different because their capacity represents the number of mice which can fit into each particular hole. Say a hole has a capacity of three, but there are five mice which can make it to that hole. Well we cannot allow more than three of those mice up in the hole. So we set the capacity of the edge to the sink to be three.

Those two leftover mice will need to find another hole or get scooped up by the apple. The very last thing we need to do to actually get the max flow is to run the solver which will return the number of safe mice, which for this configuration happens to be four. Awesome. Thank you for watching. Please like this video if you learned something, and subscribe for more mathematics and computer science videos. Thank you