CodeForces 1288F Red-Blue Graph

pufanyi

题解

发布于：Feb 7, 2020

有一张二分图，左边有 $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,v\right>$，在网络流图上建立两条边：$u\to v$，如果流表示将该边染成红色，$v\to u$，表示将改变染成黑色。

建立超源 $s$ 和超汇 $t$，考虑左边红色点，$s$ 向该点连一条下界为 $1$ 的边，表示强制流红大于流黑，对于左边黑色点，该点向 $t$ 连一条下界为 $1$ 的边，表示强制流黑大于流红，右边同理。

最后跑一遍费用流即可。

更新于：Jul 2, 2023

CodeForces

网络流