# CodeForces 1288F Red-Blue Graph Author: Fanyi Pu Published: 2020-02-07 Canonical: CodeForces 1288F Red-Blue Graph 题解。 有一张二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，$m$ 条边。每个点可能有一种颜色 `R` 或者 `B`，也可能没有，也就是 `U`。现在要给一些边染色，把边染成 `R` 要花费 $r$ 的代价，把边染成 `B` 要花费 $b$ 的代价，要求对于每个颜色为 `R` 的点，与之相邻的边中 `R` 的边**严格多于** `B` 的边；对于每个颜色为 `B` 的点，与之相邻的边中 `B` 的边**严格多于** `R` 的边。求花费最小的方案，输出任意一种，无解输出 $-1$。其中 $1 \le n_1, n_2, m, r, b \le 200$。 考虑网络流建图，对于每条边 $\left$，在网络流图上建立两条边：$u\to v$，如果流表示将该边染成红色，$v\to u$，表示将改变染成黑色。 建立超源 $s$ 和超汇 $t$，考虑左边红色点，$s$ 向该点连一条下界为 $1$ 的边，表示强制流红大于流黑，对于左边黑色点，该点向 $t$ 连一条下界为 $1$ 的边，表示强制流黑大于流红，右边同理。 最后跑一遍费用流即可。