CF212A Privatization

There is a developed network of flights between Berland and Beerland. All of them belong to the Berland state company BerAvia. Each flight connects some Berland city with some Beerland city. For each flight airplanes fly in both directions. Changes are coming to Berland — the state decided to privatize BerAvia, namely, to sell out all flights to $ t $ private companies. Each of these companies wants to get the maximal number of flights, so if the Berland flights are sold unevenly, Berland can be accused of partiality. Berland Government decided to sell the flights as evenly as possible between the $ t $ companies. The unevenness of the distribution of flights between companies is calculated as follows. For each city $ i $ (both Berland and Beerland) we'll calculate the value of  where $ a_{ij} $ is the number of flights from city $ i $ , which belong to company $ j $ . The sum of $ w_{i} $ for all cities in both countries is called the unevenness of the distribution. The distribution with the minimal unevenness is the most even one.Help the Berland government come up with the most even distribution plan of selling flights.

N/A

N/A