1. Today was just a regular day for everyone in Krypton until a news flashed that a meteor is going to destroy Krypton in X days. Krypton has N cities, some of which are connected by bidirectional roads. You are given a road map of Krypton; for every two cities Ci and Cj which are connected by a (direct) road from Ci straight to Cj you are given the value t(i,j) which is the number of days to travel from city Ci to city Cj. (You can of course also go from a city Cm to city Ck without a direct road from Cm to Ck by going through a sequence of intermediate cities connected by direct roads.)
In each city Ci the Krypton Government built qi pods to carry inhabitants in case of any calamity, which will transport them to Earth. City Ci has population pi. As soon as the people hear this news they try to save themselves by acquiring these pods either at their own city or in other city before the meteor destroys everything. Note that a pod can carry only one person. Find the largest number of invaders the Earth will have to deal with. (20 pts)
2. 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).(20 pts)
3. 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 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? (20 pts)
1
