ICPC 2012 - G. Minimum Cost Flow
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
ICPC2012TeXC++statement textstatement pdf
Source of truth
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2012/G-minimum-cost-flow. Edit
competitive_programming/icpc/2012/G-minimum-cost-flow/solution.tex to update the written solution and
competitive_programming/icpc/2012/G-minimum-cost-flow/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem statement
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem 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 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 4
7
6
1 5
2
Water 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 2
Editorial
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
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.
Source code
Code
Exact copied C++ implementation from solution.cpp.
#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
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2012\\G. Minimum Cost Flow}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#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;
}