assignment
代写Network | 代写network | 代写Algorithm | assignment代写 – 这是一个Network面向对象设计的practice, 考察Network的理解, 是比较典型的Network/network/Algorithm等代写方向, 这个项目是assignment代写的代写题目
COMP3121/9101 Term 2, 2021
assignment 4 Solutions
- There are N computers in a network, labelled{ 1 , 2 , 3 ,… , N}. There are M one-directional links which connect pairs of computers. Computer 1 is trying to send a virus to computerN. This can happen as long as there is a path of links from computer 1 to computerN. To prevent this, youve decided to remove some of the links from the network so that the two computers are no longer connected. For each link, youve calculated the cost of removing it. What is the minimum total cost to disconnect the computers as required, and which edges should be removed to achieve this minimum cost? (25 pts)
Solution: Construct a flow network with computers as vertices and with
links between computers as edges of capacity set to the price of disconnect-
ing such a link. The source of the network is set to vertex 1 and the sink
at vertexN. Find a max flow in such a network and the corresponding min
cut. Disconnect the edges which cross the cut in the direction of the parti-
tion containing 1 to the partition containingN.
- You havenwarehouses andnshops. At each warehouse, a truck is loaded with enough goods to supply one shop. There aremroads, each going from a warehouse to a shop, and driving along theith road takesdihours, where diis an integer. Design a polynomial time Algorithm to send the trucks to the shops, minimising the time until all shops are supplied. (25 pts)
Hint: Combine a binary search with a max flow. By sorting you can assume
thatdiform an increasing sequence. Fix iand consider only roads which
takedi hours to travel from a warehouse to the corresponding shop and
use max flow to see if they are enough to obtain a matching of warehouses
with shops which is of sizen. Use a binary search onito find the smallest
diwhich meets the requirements.
Solution:First sort time travel distancesdiin an increasing order; thus, we
can assume thatdi+1di. Consider a valuedifor someiand construct a
bipartite graphGiwith warehouseswjas the left side of the partition and
with shopssj(1jn). Connect all warehouses with all shops which are
within travel distance timesdi. Use max flow to see if such bipartite graph
has a perfect maximum matching of sizen. Use a binary search to find
the smallestisuch that graphGihas a matching of sizen, i.e., a matching
in which every warehouse has been matched with a shop, so that different
warehouses are assigned different shops.
- A large group of children has assembled to play a modified version of hop- scotch. The squares appear in a line, numbered from 0 ton, and a child is successful if they start at square 0 and make a sequence of jumps to reach squaren. However, each child can only jump at mostk < nsquares at a time, i.e., from squareithey can reach squaresi+ 1, i+ 2,… , i+kbut noti+k+ 1, and a child cannot clear the entire game in one jump. An additional rule of the game specifies an arrayA[1,… , n1], whereA[i] is the maximum number of children who can jump on squarei. Assuming the children co-operate, what is the largest number of children who can success- fully complete the game?(25 pts)
Hint: Connect every squareiwith squaresi+ 1,... , i+kwith a directed edge
of infinite capacity. Now limit the capacity of each square appropriately and
use max flow.
Solution:Construct a flow network with vertices 0, 1 , 2 ,... , nsuch that for
alli >0 vertexicorresponds to hopscotch squarei. Connect the additional
entry vertex 0 with vertices corresponding to squares 1 tokand every vertex
corresponding to squareiwith squaresi+1,... , i+k, all with edges of infinite
capacity. Set the capacity of each vertex 0< i < ntoA[i]. Set 0 vertex as
a source and vertexnas a sink and find max flow in such a network. The
number of kids which can reach squarenis equal to the max flow in such a
network,
- Use max flow algorithm to solve the following problem. You are given an nnchess board withkwhite bishops on the board at the given cells (ai, bi), (1ai, bin, 1ik). 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 thek bishops (recall that bishops go diagonally).(25 pts) Solution:Construct a bipartite graph withnleft side vertices representing rows of the board andnright side vertices representing columns. Connect with directed edges of capacity one every left side vertexiwith all right side
verticesjwhich satisfy the property that the cell (i, j) of the board is not under attack from one of the bishops. Add a super source and connect it with all left vertices with edges of capacity one; add a super sink and connect every right side vertex with such super sink with edges of capacity one. Find max flow; if the flow equalsnthen the problem has a solution. The rooks should be placed on cells (i, j) which correspond to edges with flow in them.