Educational Codeforces Round 80 F. Red-Blue Graph

F. Red-Blue Graph

問題概要

 二部グラフの頂点数・辺・各頂点の色(赤・青・無色のいずれか)が与えられる.

各辺はコストで赤に,コストで青に塗れる.(塗らなくてもよい)

ここで,赤い頂点に隣接する赤い辺の本数はその頂点に隣接する青い頂点より真に大きく無ければならない.青い頂点についても同様.

コストの最小値とそれを達成する辺の塗分け方を求めよ.

 解法

フローの応用らしい.