Contest Duration: - (local time) (100 minutes) Back to Home

## G - Builder Takahashi Editorial by en_translator

Construct the following directed graph $$G'$$ with $$2N$$ vertices and $$2M + N - 2$$ edges:

• The set of vertices consist of $$1, 2, \dots, N$$ and $$1', 2', \dots, N'$$.
• For each $$2 \leq i \leq N-1$$, add an edge $$i \to i'$$ with capacity $$c_i$$.
• For each $$1 \leq j \leq M$$, add edges $$a_i' \to b_i$$ and $$b'_i \to a_i$$ with capacity $$\inf$$.

Then, actually the following fact follows.

The cost $$C$$ of building walls to satisfy the condition is equal to the capacity of minimum cut on $$G'$$ with source $$1'$$ and sink $$N$$.

We will check that step-by-step.

#### Observation 1

Let $$G$$ be the undirected graph given in the original problem. There is a bijection between vertex-disjoint paths on $$G$$ between $$1 - N$$ and vertex-disjoint paths on $$G'$$ between $$1' - N$$. (A path is said to be vertex-disjoint if no vertex appears twice or more.)

Take a closer look at $$G'$$. For each $$a$$, the only edge going out from $$a$$ is $$a'$$, and all the edges going out from $$a'$$ end at vertices without primes. Therefore, a path on $$G'$$ between $$1' - N$$ can be expressed as $$1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N$$. Then, we can see that

• a vertex-disjoint path $$1=p_0,p_1,\dots,p_k=N$$ on $$G$$ and
• a vertex-disjoint path $$1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N$$ on $$G'$$

correspond one-by-one, because one can be uniquely determined by another.

#### Observation 2

Let $$S \subseteq \lbrace 2,3,\dots,N-1 \rbrace$$, then the following two propositions are equivalent.

1. When walls are built on vertices $$S$$, then Aoki cannot travel from Vertex $$1$$ to Vertex $$N$$.
2. When edges from $$i$$ to $$i'$$ are removed for all $$i \in S$$, then there will be no path $$1' \to N$$.

Proposition 1 can be reworded as follows: for all vertex-disjoint path $$p_0,p_1,\dots,p_{k-1},p_k$$ between $$1 - N$$ on $$G$$, there exists $$v \in S$$ such that $$v \in \lbrace p_1,\dots,p_{k-1}\rbrace$$.
In such case, the corresponding path $$1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N$$ on $$G'$$ defined in Observation 1 contains Edge $$v \to v'$$, so removing $$v \to v'$$ invalidates this path. We omit the details, but this sort of discussion justifies the claim.

By the observations above, the original problem is boiled down to a minimum-cut problem on $$G'$$ where only edges $$v \to v'$$ $$(2 \leq v \leq N-1)$$ are allowed to be cut.

By using AtCoder Library, it can be computed in a total of $$\mathrm{O}(N^2M)$$ time including the construction of the minimum cut, so the problem can be solved fast enough.

posted:
last update: