早稲田大学プログラミングコンテスト F. RPG

https://atcoder.jp/contests/wupc2019/tasks/wupc2019_f

The solution is easy for us, so I do not explain it here. Instead, I shall explain how to reduce the vertex cover problem to the minimum st cut problem. This technique is also known as König's theorem. If you are familiar with mincut, you might come up with how to reduce it without any hint.

A vertex set $C \subseteq V$ is called a vertex cover when all $\{u,v\} \in E$ satisfy $u \in C$ or $v \in C$ or both. The purpose of the minimum vertex cover problem is finding the minimum $|C|$ and such a $C$. An solution of this problem can be constructed by a minimum cut of the following graph.

The desired vertex set is the union of the two vertices sets, the white vertices on the left side and the orange vertices on the right side. If there is no edge from orange to white, $C$ is a vertex cover, and vice versa. The cost is one to change the color of left (right) vertex to white (orange). Thus, the two means the same thing.