<p><img src="https://gyazo.com/eaaba4778f81bf4f4751b1e923ffae74/thumb/1000" alt="image"></p>
<p>from <a href="/ja/AtCoder%20Library%20Practice%20Contest">AtCoder Library Practice Contest</a>
ACLPC_E
<a href="https://atcoder.jp/contests/practice2/tasks/practice2_e">E - MinCostFlow</a></p>
<ul>
<li><img src="https://gyazo.com/4a918321865b3d3cb12a58f05b197d54/thumb/1000" alt="image"></li>
<li><a href="/ja/%E6%9C%80%E5%B0%8F%E8%B2%BB%E7%94%A8%E6%B5%81">最小費用流</a><ul>
<li><a href="https://ei1333.github.io/luzhiled/snippets/graph/primal-dual.html">最小費用流(Primal-Dual) | Luzhiled’s memo</a></li>
</ul>
</li>
<li>「選ばれるものがK個以下」はフローの言葉にすると「容量Kの辺が繋がってる」ということ</li>
<li>選ばれるマスは容量1の辺にしておいて、最小費用流を求めた時にフローがある辺が「選ばれたマス」になる</li>
<li>選ぶとXの得をする選択肢は、選ばないとき大きな値INFの費用が掛かるようにしておいて、選ぶとINF-Xの費用がかかるようにすれば良い<ul>
<li><img src="https://gyazo.com/5a9d6fb8d110d875509cebc706ad10e7/thumb/1000" alt="image"><img src="https://gyazo.com/025a8b01a2bac694b9a720de4339d0d1/thumb/1000" alt="image"></li>
<li><img src="https://gyazo.com/eaaba4778f81bf4f4751b1e923ffae74/thumb/1000" alt="image"></li>
</ul>
</li>
</ul>


ACLPC E