# UVa 10983

## Summary

There are ${\displaystyle n}$ cities numbered from 1 to ${\displaystyle n}$ and ${\displaystyle m}$ 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 ${\displaystyle n}$-th city in ${\displaystyle d}$ days. What's the least maximum cost of a ticket they have to buy?

## Explanation

Do a binary search on the maximum cost of ticket.

For a fixed cost ${\displaystyle C}$, construct the following directed graph. The vertices are pairs (city, day). A flight of cost at most ${\displaystyle C}$ 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 ${\displaystyle z_{i}}$, and find the maximum flow between vertices s and (n, d). Its value is equal to the sum of all ${\displaystyle z_{i}}$ if and only if there is a way for all people to fly to ${\displaystyle n}$-th city in ${\displaystyle d}$ days.

```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

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