UVa 10983

From Algorithmist
Jump to navigation Jump to search

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