G. Minimum Cost Flow
Problem ID: minflow You have been hired to construct a system to transport water between two points in an old factory building using some existing components of the old plumbing. The old components consist of pipes and junctions. Junctions are points where...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
You have been hired to construct a system to transport water between two points in an old factory building using some existing components of the old plumbing. The old components consist of pipes and junctions. Junctions are points where pipes may have previously been joined. We say previously joined, because some of the old pipes were damaged and have been removed, effectively leaving open holes in the junctions to which they were connected. If water should enter one of these junctions, it would pour out of an open hole and eventually flood the building—clearly an undesirable event. You can remedy this situation by installing new pipes between some of the open holes and installing plugs to close other open holes as necessary. When you install a new pipe connecting two holes (which must be in two different junctions), the two holes are no longer open and water will be able to flow through the new pipe. The cost of installing a new pipe is equal to the distance between the centers of the two junctions the pipe connects. The cost of installing a plug in an open hole is 0.5. You are not concerned about open holes in junctions that will never be reached by water. Two of the junctions are special. One, called the source, is the point where water will be pumped into the new system. The other, called the destination, is where the water is needed. After any plugs and new pipes have been added to the system, water will be pumped into it at the source with a pressure sufficient to reach a specified height (in the absence of leaks, of course). You are allowed to select the pressure arbitrarily, and are guaranteed that the pressure will not change during the operation of the system. Naturally the pressure must be sufficient to force water up to the heights of both the source and the destination. Your task is simply to find the most inexpensive way of getting water from the source junction to the destination junction without flooding the building. The figure below corresponds to the first sample input case, where black dots represent open holes, junction 1 is the source, and junction 7 is the destination. (The position of a black dot on its circle has no significance and is used for illustration purposes only.)
3 4761 52Water flows through the system according to the laws of physics. If the pressure is sufficient to fill a junction with water, then that junction will remain filled with water. If there are pipes extending horizontally or downward from a junction, then water will also flow through those pipes. Water will also flow upward through pipes connected to a junction up to the height determined by the water pressure. Of course, if the water reaches an open hole in a junction, it will flow through the hole and flood the building. In the first sample input case, you can connect junctions 1 and 5 at a cost of 3, plug the open holes in junction 2, and set the pressure so that the water flows up to junction 7 only. The water will fill junctions 1, 2, 5, 6 and 7, and will flow no higher. A different (more expensive) solution would be to simply plug
all the holes at a total cost of 5, and let the water flow through all the junctions. You cannot solve this case by connecting junctions 1 and 6 and plugging holes in junctions 2 and 5, since junction 6 has no open holes to which a new pipe can be connected. Assume existing pipes and any new pipes do not interfere with each other or with any junctions, except those to which they are connected. That is, even if a straight line from junction A to junction B passes through junction C, any pipe from A to B will not touch C.
Input
The first line of each test case contains two integers N and M , where N (2 ≤ N ≤ 400) is the number of junctions in the building (numbered 1 through N ) and M (0 ≤ M ≤ 50 000) is the number of existing usable pipes. Each of the next N lines contains four integers xi , yi , zi , and ki satisfying −10 000 ≤ xi , yi , zi ≤ 10 000 and 0 ≤ ki ≤ 400, i = 1, 2, ..., N . The ith line describes junction i: (xi , yi , zi ) is the location of the ith junction where the z-axis is the vertical axis; ki indicates the number of open holes in the junction. Each of the next M lines contains two integers aj and bj satisfying 1 ≤ aj < bj ≤ N . The j th line indicates that pipe j connects junctions aj and bj . At most one pipe connects any pair of junctions, and no two junctions share the same coordinates. The source is junction 1, and the destination is junction N .
Output
For each case, display the case number. Then if suitable new pipes and plugs can be used to construct the desired system, display the minimum cost of connecting the source junction to the destination junction, accurate to four decimal places. If it is impossible to connect the source to the destination, display the word impossible.
Sample Input Output for Sample Input
7 6 Case 1: 4.0000
2 0 1 1 Case 2: impossible
0 0 0 2
1 0 4 3
3 0 4 3
5 0 1 1
3 0 2 0
5 0 3 0
1 2
1 3
3 4
4 7
5 7
6 7
4 1
2 0 0 0
3 0 1 0
4 1 0 1
5 1 1 1
1 2Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2012/G-minimum-cost-flow/solution.texC++ implementationcompetitive_programming/icpc/2012/G-minimum-cost-flow/solution.cppStatement textcompetitive_programming/icpc/2012/G-minimum-cost-flow/statement.txtStatement PDFcompetitive_programming/icpc/2012/G-minimum-cost-flow/statement.pdfMetadatacompetitive_programming/icpc/2012/G-minimum-cost-flow/meta.jsonYear packetcompetitive_programming/icpc/2012/contest_problems.pdf