S4. Minimum Cost Flow
레이팅 미적용의견: 0
Time limit: 3 seconds
The city of Watermoo has buildings numbered \(1, 2, \ldots, N\). The city has \(M\) pipes that connect pairs of buildings.
Due to urban planning oversights, building 1 is the only sewage
treatment plant in the city. Each pipe can be either active or
inactive. The set of active pipes forms a valid plan
if building 1 is directly or indirectly connected to each other building
using active pipes. (Pipes directly connect pairs of buildings.
Buildings \(X\) and \(Z\) are indirectly connected if \(X\) is directly or indirectly connected to
\(Y\), and \(Y\) is directly or indirectly connected to
\(Z\).)
The municipal government of Watermoo is currently operating a valid
plan of \(N-1\) pipes today, but they
think it is too expensive! Each pipe has a monthly maintenance fee that
the city must pay when it is active, and the total cost of a valid plan
is the sum of the maintenance fees of its active pipes. (Inactive pipes
cost nothing.)
Additionally, researchers at the University of Watermoo have
developed an experimental pipe enhancer which you can use on one pipe of
your choice. It will reduce that pipe’s cost from \(C\) down to \(\max(0, C-D)\), where \(D\) is the enhancer’s strength.
The city wants you to minimize the cost of the plan, and they want
you to do it quickly. Every day, the city will allow you to activate one
pipe, and deactivate another pipe. How many days do you need to make the
set of active pipes form a valid plan, whose cost is minimum among all
valid plans and all choices of enhanced pipe?
Note that it is possible that the plan becomes invalid while you are
working, but by the end it should be a valid plan.
\((1 \le N \le 100\,000, N-1 \le M \le 200\,000, 0 \le D \le 10^9)\)
\((1 \le A_i, B_i \le N, 1 \le C_i \le 10^9)\)
\(N \le 8\)
\(M \le 28\)
\(N \le 1\,000\)
\(M \le 5\,000\)
The first line will contain the integers \(N\), \(M\), and \(D\) \((1 \le N \le 100\,000, N-1 \le M \le 200\,000, 0 \le D \le 10^9)\). Each
of the next \(M\) lines contain three
integers \(A_i\), \(B_i\), and \(C_i\), which means that there is a pipe
from building \(A_i\) to building \(B_i\) that costs \(C_i\) per month when activated \((1 \le A_i, B_i \le N, 1 \le C_i \le 10^9)\). The first \(N-1\) of
these lines represent the valid plan the city is currently using.
It is guaranteed that there is at most one pipe connecting any two
buildings and no pipe connects a building to itself.
For 3 of the 15 available marks, \(N \le 8\), \(M \le 28\) and \(D=0\).
For an additional 5 of the 15 available marks, \(N \le 1\,000\) and \(M \le 5\,000\) and \(D = 0\).
For an additional 3 of the 15 available marks, \(D = 0\).
For an additional 2 of the 15 available marks, \(N \le 1\,000\) and \(M \le 5\,000\).
Output one integer on a single line, the minimum number of days to
complete this task. If the initial valid plan is already an optimal
plan, then output \(0\).
4 4 0
1 2 1
2 3 2
3 4 1
4 1 11Note that it does not matter which pipe you use the pipe enhancer on
because \(D = 0\), so it will not
affect the maintenance fee of any pipe.
On the first day, you should deactivate the pipe from building \(2\) to \(3\) and activate the pipe from building
\(4\) to \(1\).
5 6 2
1 2 5
2 3 5
1 4 5
4 5 5
1 3 1
1 5 12One solution using the minimum number of days is to first use the
pipe enhancer on the pipe from building \(1\) to \(2\) to decrease its cost to 3. Then on the
first day, replace the pipe from building \(2\) to \(3\) with the pipe from building \(1\) to \(3\), and on the second day replace the pipe
from \(1\) to \(4\) with the pipe from building \(1\) to \(5\). Note that the cost of the optimal plan
is 10.
Additionally, there are no solutions where you use the pipe enhancer on
the pipe from building \(1\) to \(3\) or the pipe from building \(1\) to \(5\). Doing so would make that pipe have a
maintenance fee of 0, and then any optimal plan would have cost 11 (and
we have already seen that we can achieve a cost of 10).
4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 7158278840The initial valid plan is already an optimal plan. Be careful of
integer overflow when implementing your solution.
평가 및 의견
S4. Minimum Cost Flow
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S4. Minimum Cost Flow