CF1288F Red-Blue Graph

给定一个二分图：第一部分有 $n_1$ 个顶点，第二部分有 $n_2$ 个顶点，共有 $m$ 条边。图中可能存在重边。 初始时，每条边都是无色的。对于每条边，你可以选择保持无色（免费），将其涂成红色（需花费 $r$ 个金币），或者将其涂成蓝色（需花费 $b$ 个金币）。每条边不能同时被涂成红色和蓝色。 图中的顶点分为三种类型——无色、红色和蓝色。带颜色的顶点对相邻边的颜色有额外约束： - 对于每个红色顶点，与其相连的红色边的数量必须严格大于与其相连的蓝色边的数量； - 对于每个蓝色顶点，与其相连的蓝色边的数量必须严格大于与其相连的红色边的数量。 无色顶点没有额外约束。 你的目标是对部分（也可以不对任何）边进行染色，使得所有约束都被满足，并且在所有可行方案中，总花费最小。

第一行包含五个整数 $n_1$、$n_2$、$m$、$r$ 和 $b$（$1 \le n_1, n_2, m, r, b \le 200$），分别表示第一部分的顶点数、第二部分的顶点数、边数、将一条边染成红色的花费、将一条边染成蓝色的花费。 第二行包含一个长度为 $n_1$ 的字符串。每个字符为 U、R 或 B。如果第 $i$ 个字符为 U，则第一部分的第 $i$ 个顶点为无色；R 表示红色顶点，B 表示蓝色顶点。 第三行包含一个长度为 $n_2$ 的字符串。每个字符为 U、R 或 B，表示第二部分各顶点的颜色，含义同上。 接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i \le n_1$，$1 \le v_i \le n_2$），表示一条连接第一部分第 $u_i$ 个顶点和第二部分第 $v_i$ 个顶点的边。 图中可能存在重边。

如果不存在满足所有约束的染色方案，输出一个整数 $-1$。 否则，输出一个整数 $c$，表示染色的最小总花费，以及一个长度为 $m$ 的字符串。第 $i$ 个字符为 U 表示第 $i$ 条边保持无色，R 表示染成红色，B 表示染成蓝色。如果有多种最小花费的方案，输出任意一种均可。

由 ChatGPT 4.1 翻译