# UVa 10983

## 10983 - Buy one, get the rest free[edit]

## Summary[edit]

There are cities numbered from 1 to and flights. For each flight, you know its departure and arrival cities and days, cost of ticket and capacity (number of people it carries.) A certain number of people from each city needs to gather in the -th city in days. What's the least maximum cost of a ticket they have to buy?

## Explanation[edit]

Do a binary search on the maximum cost of ticket.

For a fixed cost , construct the following directed graph. The vertices are pairs (city, day). A flight of cost at most from city u to city v on day e corresponds to an edge from (u, e) to (v, e+1) of capacity, equal to the flight's capacity. For each city i and each day j<d, there is an edge of infinite capacity from (i, j) to (i, j+1). Add a vertex s, connected to every vertex (i, 0) with an edge of capacity , and find the maximum flow between vertices s and (n, d). Its value is equal to the sum of all if and only if there is a way for all people to fly to -th city in days.

## Solutions[edit]

## Input[edit]

5 5 4 5 1 5 100 30000 0 2 4 10 10000 0 2 4 10 10000 1 4 5 25 25000 2 2 5 100 40000 3 1 20 0 5 100 2 1 1 1 2 99 10400 0 100 0 2 1 0 0 100 2 10 0 100 100 1 10 0 100

## Output[edit]

Case #1: 30000 Case #2: Impossible Case #3: 0 Case #4: Impossible Case #5: 0