Methods of applying the algorithm for finding the maximum flow in the network

Introduction

The maximum flow problem is classical and has many uses. Let me remind you of the problem. Given a weighted oriented graph with non-negative weights (throughput). Two vertices are distinguished: the source S and the drain T such that any other vertex lies on the path from S to T. The stream is the function F: V x V with such properties.

1. Bandwidth limiting. The flow along the edge can not be greater than its (edge) throughput.
2. Antisymmetry. For each edge (u, v): F (u, v) = -F (v, u).
3. Saving flow. For each vertex (except S and T ), the amount of incoming flow (negative) is equal to the number of outgoing flow (positive). That is, the algebraic sum of flows for each vertex (except S and T ) is zero.

In this post you can get acquainted with the implementation of the problem.

Let us proceed directly to the typical tasks that are reduced to the algorithm for finding the maximum flow in the network. Often it is not easy to identify the flow in such tasks.


')

Tasks

1. The maximum matching problem. At the entrance is given N - the number of boys, M - the number of girls and a list of which boy wants to dance with which of the girls (there may be several of them). It is necessary to determine the maximum number of simultaneously dancing couples.
   
   
   

   Decision

   
   To solve this problem, you can use the Kuhn algorithm , but since we decided to reduce everything to the stream - let's do it. For this there is not enough source and drain. Let's add them! “On the left,” we add a fictitious vertex and draw edges to all boys weighing 1. From boys to girls, we already have edges, we also put down the price for them. .
2. Spoiled parquet. In NxM parquet, some cells may be damaged. They must be closed with new tiles. The tiles are 2x1 in size (can be rotated, but not cut) at the price A, and 1x1 at the price B. The question is what minimum amount should be spent to lay damaged floor tiles. Naturally, new tiles should not overlap any other tiles.
   
   

   Decision

   
   For a start, make sure that 2 * B> A. Otherwise, it is more profitable to pave only 1x1 tiles and there is nothing more to count. Further, our task is to maximize the number of tiles at the cost of A.
   Let's paint our parquet according to the chessboard principle. Obviously, then one end of a 2x1 tile will lie on a black cell, the other on a white one. So, we construct a bichromatic graph, one share of which will contain white cells, the other - black. Ribs weighing 1 will be drawn between the adjacent cells. Add a source with edges to white vertices with a weight to infinity (a fairly common technique) and a drain with edges from black cells weighing also to infinity. Let f - the value of the found maximum flow between the source and drain. Ie we found the number of tiles 2x1. The answer to the problem is the value of f * A + (Kf) * B, where K is the total number of damaged cells.
   Source: Kharkov Winter Programming School, 2009, Day 3
   
3. Task painting Given the matrix N * M with cells painted either black or white. W - the price of repainting a black square to white, B - white to black. After repainting, it is necessary to draw a gray line between all neighboring squares of different colors, the cost of G. It is necessary to repaint the matrix so or very little (or nothing) to spend the minimum amount.
   
   
   

   Decision

   
   The extreme case: if the matrix is ​​all the same color - the answer is 0.
   Add a dummy source and drain. From the source to all the white peaks we draw edges, weighing in B (the price of repainting is black). From black vertices to the drain we draw edges, weighing in W (the price of repainting is white). And between all adjacent vertices (whether they are of the same or different colors), put an edge with a weight in G (gray line). The magnitude of the maximum flow will be the answer to the problem.
   Source: All-Ukrainian School Olympiad in Informatics, 2007, Day 1
   
4. A problem with constraints on vertices. Let it be necessary to find the value of the maximum flow and the vertices are constrained by how much they can skip.
   
   

   Decision

   
   All we need is to divide each vertex into two, and put an edge between them, weighing in the bandwidth limit of this vertex.
5. Minimum cut. Dan graph. How many vertices need to be removed so that there is no path from A to B?
   
   

   Decision

   
   In the classical problem of minimal cut, you need to delete the edges. No problem! We divide the vertices into 2, and put an edge between them, weighing 1. Then the answer to the problem is to find the minimum cut in the graph (which is the maximum flow).
   Source: Kharkov Winter Programming School, 2009, Day 3
   
6. Poetry writer. There is a deterministic finite automaton with one initial state A and one final B. Each transition is given by a triple of numbers (i, j, k), a transition from state i to state j along edge k.
   After the transition from the automaton from i to j along the edge k, all transitions from i along edge k are erased, as well as all transitions into j along edge k. It is required to output the number of paths from A to B using such an automaton.
   
   

   Decision

   
   The task is to find the maximum number of paths, and more than one edge of the same color does not extend from one vertex. We reduce the problem to finding the maximum flow. For each vertices, create k + 1 vertices in the rebuilt network. The first vertex will be the entrance, the remaining vertices will represent the colors. From the top of the entrance we draw an edge with a bandwidth of 1 to each of the k vertices corresponding to the color. From the vertex corresponding to color i, we draw all edges of color i to the inputs of the ends of the edges. Having found the maximum flow in such a network, we obtain the maximum number of paths satisfying the required property.
   Source: Kharkov Winter Programming School, 2009, Day 4
   
7. Collecting coins. There are n collectors and m kinds of coins. To join a club, you must have at least one coin of each type. You (you have number 1) can change with collectors available coins. Any collector will exchange his coin a for your coin b if he has more than one coin of type a and there is not a single coin of type b . You, in turn, can break this rule. You need to collect as many types of coins as possible for a known situation with all collectors.
   
   

   Decision

   
   Let's build a network. Let's create one vertex for each type of coins. These tops will match your coins. We need to collect as many unique coins as possible, so we draw a edge of throughput 1 into the drain from each such vertex. In the vertices corresponding to the coins that you have initially, we will draw an edge, whose capacity is equal to the number of such coins you have.
   For each member of the club (except for 1, Ie, you) we will get one vertex. This top can accept no more than one coin, which it does not have and give away.
   no more than k-1 coins, of which he has k (k> 1). Naturally, a member of the club gives one coin in return for one received.
   Thus, in each such vertex, one needs to draw a bandwidth edge 1 of the vertices of the corresponding coins that this member does not have. And from these vertices you need to hold the edges with a bandwidth of k _i - 1 to the vertex i, corresponding to the coins, which the club member has more than one.
   The constructed network reflects the exchange processes in the club. The maximum flow in such a network will be equal to the maximum number of coins that can be collected by you.
   Source: Kharkov Winter Programming School, 2009, Day 4
   
8. Circulation. The cooling system of the reactor is a set of pipes connecting the nodes. Fluid flows through the pipes, and for each pipe the direction in which it must flow is strictly defined. The cooling system nodes are numbered from 1 to N. The cooling system must be designed so that for each node per unit of time the amount of liquid flowing into the node is equal to the amount of liquid flowing from the node. Each pipe has a capacity c _ij . In addition, to ensure sufficient cooling, it is required that at least l _ij units of fluid per unit of time flow through the pipe. That is, for the pipe leading from the i-th node to the j-th l _ij ≤ f _ij ≤ c _ij should be performed.
   A description of the cooling system. We need to figure out how to pour the liquid through the pipes so that all the specified conditions are fulfilled.
   
   

   Decision

   
   This is the task of finding circulation in the network with given lower restrictions on the edges. If the edge (u, v) has to flow in the segment [l, r], then in the rebuilt network there will be three edges (from where, where, weight): (u, v, r - l), (S, v, l ), (u, T, l). S, T - additionally introduced drain and source, respectively. In fact, we pass along the edge the necessary minimum flow, after which we balance it so as to obtain circulation.
   Source: Kharkov Winter Programming School, 2009, Day 4
   
9. Dancing again. N boys and n girls are invited to the party. They want to dance a few rounds.
   In each round, guests are divided into n dancing couples. Each guest should be in a couple, each couple should consist of one boy and one girl. In each round, each boy must dance with another girl. Some boys and girls don't like each other. Each boy can dance with no more than k girls that he doesn’t like. Similarly, each girl can dance with no more than k boys that she doesn’t like.
   There is information about whether the i-th boy and the j-th girl like each other (1 ≤ i, j ≤ n). Find the greatest number of rounds you can dance at a party.
   
   

   Decision

   
   Consider the following problem: can dances continue exactly m rounds? If we can answer this question, then with a binary search we will find the greatest m for which dancing is possible.
   Construct a graph with one source and one drain (black vertices). Red tops represent boys, gray - girls. If a boy and a girl like each other, then we will draw between them the edge of a single bandwidth (in the figure there are two edges - upper and lower). Otherwise, add blue and green vertices as shown in the figure and set the edge bandwidth between the corresponding blue and green vertices to 1.
   Blue and green peaks form a “protective” level. The connection of boys with girls who do not like each other, will be held along the edges of the protective level. Each boy can dance with no more than k girls that he doesn’t like. Set the bandwidth of the edges between red and blue, green and gray vertices equal to k. Thus, between each boy and each girl a link will be established through the edge, either directly or through the tops of the protective level.
   Dancing must go on exactly m rounds. Set the bandwidth of the edges between the source and the red vertices, and also between the gray vertices and the drain equal to m.
   
   Find the maximum flow in the graph. Dances can continue exactly m rounds if and only if the maximum flow is equal to n * m, where n is the number of boys.
   Source: Sevastopol Summer School on Programming, 2010, Day 4
   

Conclusion

We considered a negligible part of an immense set of tasks, which boil down to finding the maximum flow in the network. And this does not affect the maximum flow of the minimum cost. Such tasks are distinguished by their beauty in the solution. The programmer, knowing the standard algorithm for finding the maximum flow, needs only to construct a graph corresponding to the task and to start up the flow.