COMP3121/9101
Algorithm Design
Copyright By PowCoder代写 加微信 powcoder
Problem Set 4 – Maximum Flow
[K] – key questions [H] – harder questions [E] – extended questions [X] – beyond the scope of this course
1 SECTION ONE: MAXIMUM FLOW 2
2 SECTION TWO: MINIMUM CUT 4
3 SECTION THREE: BIPARTITE MATCHING 5
Problem Set 4 SECTION ONE: MAXIMUM FLOW
§ SECTION ONE: MAXIMUM FLOW
[K] Exercise 1. Several families are coming to a birthday celebration in a restaurant. You have arranged that v
many tables will serve only vegetarian dishes, p many tables will not serve pork and r many remaining tables will serve
food with pork. You know that V many families are all vegetarians, P1 many families do not eat pork but do not mind
eating vegetarian dishes, P2 many families do not eat pork but hate vegetarian dishes. Also R1 many families have no
dietary restrictions and would also not mind eating vegetarian dishes or food without pork, R2 many families have no
dietary restrictions but hate vegetarian dishes but can eat food without pork. Finally, S many families are from Serbia
and cannot imagine not eating pork. You are also given the number of family members in each family and the number
of seats at each table.
In total, there are m families and n tables. You must place the guests at the tables so that their food preferences are
respected and no two members from the same family sit at the same table. Your algorithm must run in time polynomial
in m and n, and in case the problem has no solutions, your algorithm should output “no solution”.
[K] Exercise 2. A band of m criminals has infiltrated a secure building, which is structured as an n× n square grid
of rooms, each of which has a door on all of its sides. Thus,
• from an internal room, we can move to any of the four neighbouring rooms
• from a room on the side of the building (or edge room), we can move to three other rooms or leave the building
• from a corner room, we can move to two other rooms or leave the building
The criminals were able to shut down the building’s security system before entering, but during their nefarious activities,
the security system became operational again, so they decided to abort the mission and attempt to escape. The building
has a sensor in each room, which becomes active when an intruder is detected, but only triggers the alarm if it is activated
again. Thus, the criminals may be able to escape if they can all reach the outside of the building without any two of
them passing through the same room.
Design an algorithm which runs in time polynomial in m and n and, given the m different rooms which the criminals
occupy when the security system is reactivated, determines whether all m criminals can escape without triggering the
[H] Exercise 3. You have been told of the wonder and beauty of a very famous painting. It is painted in the
hyper-modern style, and so it is simply an n× n grid of squares, with each square coloured either black or white.
You have never seen this picture for yourself but have been told some details of it by a friend. Your friend has told you
the value of n and the number of white squares in each row and each column. Additionally, your friend has also been
kind enough to tell you the specific colour of some squares: some squares are black, some are white, and the rest they
simply could not remember.
The more details they tell you, the more amazing this painting becomes but you begin to wonder that perhaps it’s
simply too good to be true. Thus, you wish to design an algorithm which runs in time polynomial in n and determines
whether or not such a painting can exist.
[H] Exercise 4. Alice is the manager of a café which supplies n different kinds of drink and m different kinds of
One day the materials are in short supply, so she can only make ai cups of each drink type i and bj servings of each
dessert type j.
On this day, k customers come to the café and the ith of them has pi favourite drinks (ci,1, ci,2…, ci,pi) and qi favourite
COMP3121/9101 – Term 3, 2022 2
Problem Set 4 SECTION ONE: MAXIMUM FLOW
desserts (di,1, di,2, . . . , di,qi). Each customer wants to order one cup of any one of their favourite drinks and one serving
of any one of their favourite desserts. If Alice refuses to serve them, or if all their favourite drinks or all their favourite
desserts are unavailable, the customer will instead leave the café and provide a poor rating.
Alice wants to save the restaurant’s rating. From her extensive experience with these k customers, she has listed out
the favourite drinks and desserts of each customer, and she wants your help to decide which customers’ orders should
be fulfilled.
Design an algorithm which runs in time polynomial in n, m and k and determines the smallest possible number of poor
ratings that Alice can receive, given that:
• all pi and all qi are 1 (i.e. each customer has only one favourite drink and one favourite dessert),
• there is no restriction on the pi and qi.
COMP3121/9101 – Term 3, 2022 3
Problem Set 4 SECTION TWO: MINIMUM CUT
§ SECTION TWO: MINIMUM CUT
[K] Exercise 5. There are n cities (labelled 1, 2, . . . , n), connected by m bidirectional roads. Each road connects two
different cities. A pair of cities may be connected by multiple roads. A well-known criminal is currently in city 1 and
wishes to get to the city n via road. To catch them, the police have decided to block the minimum number of roads
possible to make it impossible to get from city 1 to city n. However, some roads are major roads. In order to avoid
disruption, the police cannot close any major roads.
Your goal is to find the minimum number of roads to block to prevent the criminal from going from city 1 to city
n, or report that the police cannot stop the criminal. Design an algorithm which achieves this goal and runs in time
polynomial in n and m.
[K] Exercise 6. In the country of Pipelistan there are several oil wells, several oil refineries and many distribution
hubs all connected by oil pipelines. To visualise Pipelistan’s oil infrastructure, just imagine a undirected graph with k
source vertices (the oil wells), m sinks (refineries) and n vertices which are distribution hubs linking (unidirectional)
pipelines incoming to this vertex with the outgoing pipelines from that vertex.
You are given the graph and the capacity C(i, j) of each pipeline joining a vertex i with vertex j. You want to install
the smallest possible number of flow meters on some of these pipelines so that the total throughput of oil from all the
wells to all refineries can be computed exactly from the readings of all of these meters. Each meter shows the direction
of the flow and the quantity of flow per minute. Design an algorithm which runs in time polynomial in k, m and n and
decides on which pipelines to place the flow meters.
[K] Exercise 7. Assume that you are given a network flow graph with n vertices, including a source s, a sink t and
two other distinct vertices u and v, and m edges. Design an algorithm which runs in time polynomial in n and m and
returns the smallest capacity-cut among all cuts for which the vertex u is on the same side of the cut as the source s
and vertex v is on the same side as the sink t.
[K] Exercise 8. Assume that you are given a network flow graph with n vertices, including a source s, a sink t and
two other distinct vertices u and v, and m edges. Design an algorithm which returns a smallest capacity cut among all
cuts for which vertices u and v are in the same side of the cut.
[K] Exercise 9. Given an undirected graph with vertices numbered 1, 2, . . . , n and m edges, design an algorithm
which runs in time polynomial in n and m and partitions the vertices into two disjoint subsets such that:
• vertex 1 and n are in different subsets, and
• the number of edges with both ends in the same subset is maximised.
[K] Exercise 10. You know that n + 2 spies S, s1, s2, . . . , sn and T are communicating through m communication
channels; in fact, for each i and each j you know if there is a channel through which spy si can send a secret message to
spy sj or if there is no such a channel (i.e., you know what the graph with spies as vertices and communication channels
as edges looks like). Design an algorithm which runs in time polynomial in n and m that prevents spy S from sending
a message to spy T by:
(a) compromising as few channels as possible;
(b) bribing as few of the other spies as possible.
COMP3121/9101 – Term 3, 2022 4
Problem Set 4 SECTION THREE: BIPARTITE MATCHING
§ SECTION THREE: BIPARTITE MATCHING
[K] Exercise 11. You are manufacturing integrated circuits from a rectangular silicon board that is divided into an
m× n grid of squares. Each integrated circuit requires two adjacent squares, either vertically or horizontally, that are
cut out from this board. However, some squares in the silicon board are defective and cannot be used for integrated
circuits. For each pair of coordinates (i, j), you are given a boolean di,j representing whether the square in row i and
column j is defective or not. Design an algorithm which runs in time polynomial in m and n and determines the
maximum number of integrated circuits that can be cut out from this board.
[K] Exercise 12. You are hosting a game festival where n players may participate in m games. During the festival
event, each individual player has a preference of k candidates (k is the same for all players) – the i-th player has
candidates ai1, ai2, . . . , aik. One player may choose at most one game (he may choose not to play, though) among those
candidates.
For every game, the player having the highest score would receive a prize. It is guaranteed that no two players would
share the same highest score (so you wouldn’t have to worry about causing conflict between winners!). As the host
of this game festival, you would like to know how many prizes should you prepare to ensure no player would end up
receiving no prizes. That is, calculate the maximum number of distinct games chosen by players.
[K] Exercise 13. You are given an n × n chessboard. with k white bishops on the board at the given cells (ai, bi),
where 1 ≤ ai, bi ≤ n for each 1 ≤ i ≤ k. You have to determine the largest number of black rooks which you can place
on the board so that no two rooks are in the same row or in the same column or are under the attack of any of the k
bishops. Recall that bishops attack diagonally.
[H] Exercise 14. You are the head of n spies, who are all wandering in a city. On one day you received a secret
message that the bad guys in this city are going to arrest all your spies, so you’ll have to arrange for your spies to run
away and hide in strongholds. You have T minutes before the bad guys arrive. Your n spies are currently located at
(x1, y1), (x2, y2), . . . , (xn, yn),
and your m strongholds are located at
(a1, b1), (a2, b2), . . . , (am, bm).
The ith spy can move vi units per minute, and each stronghold can hold only one spy.
Design an algorithm which runs in time polynomial in n and m determines which spies should be sent to which
strongholds so that you have the maximum number of spies hiding from the bad guys.
[H] Exercise 15. You have n warehouses and n shops. At each warehouse, a truck is loaded with enough goods to
supply one shop. There are m roads, each going from a warehouse to a shop, and driving along the i-th road takes di
hours, where di is an integer. Design a polynomial time algorithm to send the trucks to the shops, minimising the time
until all shops are supplied.
Hint: Combine binary search with a max flow.
[H] Exercise 16. There are n boys and n girls at a party. Whenever a song starts, they will form exactly n pairs to
dance and no boy will dance with the same girl twice.
Some pairs of boys and girls like each other, and all other pairs of boys and girls dislike each other. Every boy will
COMP3121/9101 – Term 3, 2022 5
Problem Set 4 SECTION THREE: BIPARTITE MATCHING
dance with at most k girls that he dislikes, and each girl will dance with at most k boys that she dislikes where k < n. As the DJ, it is your job to determine the maximum number of songs to play such that it is possible for pairs to be formed that satisfy the above requirement. Design a O(n4 log n) algorithm that achieves this task. Hint: Start with the case where k = 0 and fix a capacity x for edges between each boy and girl. How can you generalise this to arbitrary k? COMP3121/9101 – Term 3, 2022 6 SECTION ONE: MAXIMUM FLOW SECTION TWO: MINIMUM CUT SECTION THREE: BIPARTITE MATCHING 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com