这是一篇来自北美的算法代写assignment

1. There are N computers in a network, labelled f1; 2; 3; : : : ;Ng. There are M one-directional links which connect pairs of computers. Computer 1 is trying to send a virus to computer N. This can happen as long as there is a path of links from computer 1 to computer N. To prevent this, you’ve decided to remove some of the links from the network so that the two computers are no longer connected. For each link, you’ve 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)

2. 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 ith 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. (25 pts)
Hint: Combine a binary search with a max ow. By sorting you can assume that di form an increasing sequence. Fix i and consider only roads which take  di hours to travel from a warehouse to the corresponding shop and use max ow to see if they are enough to obtain a matching of warehouses with shops which is of size n. Use a binary search on i to nd the smallest di which meets the requirements.

3. A large group of children has assembled to play a modied version of hop-scotch. The squares appear in a line, numbered from 0 to n, and a child is successful if they start at square 0 and make a sequence of jumps to reach square n. However, each child can only jump at most k < n squares at a time, i.e., from square i they can reach squares i + 1; i + 2; : : : ; i + k but not i + k + 1, and a child cannot clear the entire game in one jump. An additional rule of the game species an array A[1; : : : ; n 1], where A[i] is the maximum number of children who can jump on square i. Assuming the children co-operate, what is the largest number of children who can success-fully complete the game?(25 pts)

Hint: Connect every square i with squares i+1; : : : ; i+k with a directed edge of innite capacity. Now limit the capacity of each square appropriately and use max ow.

4. Use max ow algorithm to solve the following problem. You are given a usual n  n chess board with k white bishops on the board at the given cells (ai; bi), (1  ai; bi  n, 1  i  k). You have to determine the largest number of black rooks 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 go diagonally).(25 pts)