How to recognize max-flow problems? Often they are hard to detect and usually boil down to maximizing the movement of something from a location to another. We need to look at the constraints when we think we have a working solution based on maximum flow – they should suggest at least an O(N³) approach. If the number of locations is large, another algorithm (such as dynamic programming or greedy), is more appropriate.
The problem description might suggest multiple sources and/or sinks. For example, in the sample statement in the beginning of this article, the company might own more than one factory and multiple distribution centers. How can we deal with this? We should try to convert this to a network that has a unique source and sink. In order to accomplish this we will add two “dummy” vertices to our original network – we will refer to them as super-source and super-sink. In addition to this we will add an edge from the super-source to every ordinary source (a factory). As we don’t have restrictions on the number of trucks that each factory can send, we should assign to each edge an infinite capacity. Note that if we had such restrictions, we should have assigned to each edge a capacity equal to the number of trucks each factory could send. Likewise, we add an edge from every ordinary sink (distribution centers) to the super-sink with infinite capacity. A maximum flow in this new-built network is the solution to the problem – the sources now become ordinary vertices, and they are subject to the entering-flow equals leaving-flow property. You may want to keep this in your bag of tricks, as it may prove useful to most problems.
This is one of the most important applications of maximum flow, and a lot of problems can be reduced to it. A matching in a graph is a set of edges such that no vertex is touched by more than one edge. Obviously, a matching with a maximum cardinality is a maximum matching. For a general graph, this is a hard problem to deal with.
Problem Statement
This problem asks us to place a maximum number of rooks on a rows x cols chessboard with some squares cut out. The idea behind this might be a little hard to spot, but once this is done, we get into a standard maximum bipartite-matching problem.
Notice that at most one rook can be placed on each row or column. In other words, each row corresponds at most to one column where a rook can be placed. This suggests a bipartite matching where set A is composed of elements corresponding to every row of the board, while set B consists of the columns. For each row add edges to every column if the corresponding square is not cut out of the board. Now we can just run maximum bipartite-matching in this network and compute the result. Since there are at most rows * cols edges, the time complexity of the algorithm is: O(rows² * cols)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class RookAttack { // a list of the non-empty squares for each row
vector lst[300];
// in this arrays we keep matches found to every row and column
int row_match[300], col_match[300];
// we search for an augmenting path starting with row source
bool find_match(int source) {
// from[x] = the row-vertex that precedes x in the path
int from[300], where, match;
memset(from, -1, sizeof(from));
from[source] = source;
deque q;
q.push_back(source);
bool found_path = false;
while (!found_path && !q.empty()) {
// where = current row-vertex we are in
where = q.front();
q.pop_front();
// we take every uncut square in the current row
for (int i = 0; i < lst[where].size(); ++i) {
match = lst[where][i];
// next = the row matched with column match
int next = col_match[match];
if (where != next) {
// no row matched with column match thus
we found an augmenting path
if (next == -1) {
found_path = true;
break;
}
// a check whether we already visited
the row - vertex next
if (from[next] == -1) {
q.push_back(next);
from[next] = where;
}
}
}
}
if (!found_path)
return false;
while (from[where] != where) {
// we de-match where from its current match (aux)
and match it with match
int aux = row_match[where];
row_match[where] = match;
col_match[match] = where;
where = from[where];
match = aux;
}
// at this point where = source
row_match[where] = match;
col_match[match] = where;
return true;
}
public:
int howMany(int rows, int cols, vector cutouts) { // build lst from cutouts; column j should appear in
row 's i list if square (i, j) is present on the board
int ret = 0;
memset(row_match, -1, sizeof(row_match));
memset(col_match, -1, sizeof(col_match));
// we try to find a match for each row
for (int i = 0; i < rows; ++i)
ret += find_match(i);
return ret;
}
};
Let’s take a look at the DFS version, too. We can implement the find_match function like this: for each non-empty square in the current row try to match the row with its corresponding column and call find_match recursively to attempt to find a new match for the current match (if the current match exists – if not, an augmenting path is found) of this column. If one is found, we can perform the desired match. Note that to make this run in time we must not visit the same column (or row) twice. Notice the C++ code below is extremely short:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool find_match(int where) {
// the previous column was not matched /n
if (where == -1)
return true;
for (int i = 0; i < lst[where].size(); ++i) {
int match = lst[where][i];
if (visited[match] == false) {
visited[match] = true;
if (find_match(col_match[match])) {
col_match[match] = where;
return true;
}
}
}
return false;
}
This runs in time because the number of augmenting paths is the same for both versions. The only difference is that BFS finds the shortest augmenting-path while DFS finds a longer one. As implementation speed is an important factor in TopCoder matches, in this case it would be a good deal to use the slower, but easier DFS version.
The following version of the problem is left as an exercise for the reader: to try and place as many rooks as possible on the board in such a way that the number of rooks on each row is equal to the number of rooks on each column (it is allowed for two rooks to attack each other).
Problem Statement
In this problem we are given a set of requirements, each stating that a number of classes should be taken from a given set of classes. Each class may be taken once and fulfills a single requirement. Actually, the last condition is what makes the problem harder, and excludes the idea of a greedy algorithm. We are also given a set of classes already taken. If it weren’t for this, to ensure the minimality of the return, the size of the returned string would have been (if a solution existed) the sum of the number of classes for each requirement. Now as many classes as possible must be used from this set.
At first glance, this would have been a typical bipartite-matching problem if every requirement had been fulfilled by taking just a single class. Set A would have consisted of the classes available (all characters with ASCII code in the range 33-126, except for the numeric characters ’0′-’9′), while the set of requirements would have played the role of set B. This can be taken care of easily. Each requirement will contribute to set B with a number of elements equal to the number of classes that must be taken in order to fulfill it – in other words, split each requirement into several requirements. At this point, a bipartite-matching algorithm can be used, but care should be allotted to the order in which we iterate through the set of classes and match a class with a requirement.
Problem Statement
In this problem we have to match each of the cars with a parking spot. Additionally the time it takes for all cars to find a parking spot must be minimized. Once again we build a bipartite graph: set A is the set that consists of the cars and set B contains the parking spots. Each edge connecting elements from different sets has as the cost (and not the capacity!) the time required for the car to get to the parking spot. If the spot is unreachable, we can assign it an infinite cost (or remove it). These costs are determined by running breadth-first search.
For solving it, assume that the expected result is less than or equal to a constant D. Then, there exists a matching in which each edge connecting a car and a parking spot has the cost less than or equal to D. Thus, removing edges with cost greater than D will have no effect on the solution. This suggests a binary search on D, removing all edges with cost greater than D, and then performing a maximum bipartite-matching algorithm. If a matching exists in which every car can drive to a parking spot, we can decrease D otherwise we must increase it.
However, there is a faster and more elegant solution using a priority-first search. Instead of keeping D fixed as above, we could try to successively increase D whenever we find that it is too low. We will start with D = 0. Then we iterate through each of the cars and try to find an augmenting path in which no edge has a cost larger than D. If none exists, we increase D until one path exists. Obviously, we will increase it with the smallest possible amount. In order to achieve this, we will search for the augmenting path with the smallest cost – the cost of the path is the maximum cost of an edge on that path. This can be done with a priority-first search similar to the PFS augmenting-path algorithm presented in the first section of the article. C++ code follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct node {
int where, cost, from;
node(int _where, int _cost, int _from): where(_where),
cost(_cost), from(_from) {};
};
bool operator < (node a, node b) {
return a.cost > b.cost;
}
int minTime(vector park) {
// build a cost matrix cost[i][j] = cost of getting from car i to
parking spot j, by doing a BFS
// vertices 0, 1, ..., N - 1 will represent the cars, and
vertices N, N + 1, ..., N + M - 1 will represent
//the parking spots; N + M will be the super-sink
int D = 0, sink = N + M;
int car_match[105], park_match[105];
memset(car_match, -1, sizeof(car_match));
memset(park_match, -1, sizeof(park_match));
for (int source = 0; source < N; ++source) {
bool visited[210];
memset(visited, false, sizeof(visited));
int from[210];
memset(from, -1, sizeof(from));
priority_queue pq;
pq.push(node(source, 0, -1));
while (!pq.empty()) {
int cst = pq.top()
.cost, where = pq.top()
.where,
_from = pq.top()
.from;
pq.pop();
if (visited[where]) continue;
visited[where] = true;
from[where] = _from;
// if where is a car try all M parking spots
if (where < N) {
for (int i = 0; i < M; ++i) {
// if the edge doesn't exist or this car is already matched with this parking spot
if (cost[where][i] == infinity ||
car_match[where] == i) continue;
int ncst = max(cst, cost[where][i]);
// the i-th parking spot is N + i
pq.push(node(N + i, ncst, where));
}
} else {
// if this parking spot is unmatched we found the augmenting path with minimum cost
if (park_match[where - N] == -1) {
from[sink] = where;
// if D needs to be increased, increase it
D = max(D, cst);
break;
}
// otherwise we follow the backward edgeint next = park_match[where - N];
int ncst = max(cst, cost[next][where]);
pq.push(node(next, ncst, where));
}
}
int where = from[sink];
// if no augmenting path is found we have no solution
if (where == -1)
return -1;
// follow the augmenting pathwhile (from[where] > -1) {
int prev = from[where];
// if where is a parking spot the edge (prev, where) is a forward edge and the match must be updated
if (where >= N) {
car_match[prev] = where;
park_match[where - N] = prev;
}
where = prev;
}
}
return D;
}
Here are some problems to practice:
PlayingCubes – for this one ignore the low constraints and try to find a max-flow algorithm
DataFilter – be warned this is the hard problem from the TCCC 2004 Finals and is tough indeed!
Some other problems from http://acm.uva.es/p/ : 563, 753, 820, 10122, 10330, 10511, 10735.
For any questions or comments please use the Forums.