1672 - #6009. 「网络流 24 题」软件补丁

1672. #6009. 「网络流 24 题」软件补丁

时间限制 1000 ms 内存限制 256 MB

某公司发现其研制的一个软件中有 $n$ 个错误，随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于每一个补丁 $i$ ，都有 $2$ 个与之相应的错误集合 $B_1(i)$ 和 $B_2(i)$ ，使得仅当软件包含 $B_1(i)$ 中的所有错误，而不包含 $B_2(i)$ 中的任何错误时，才可以使用补丁 $i$ 。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$ ，而同时加入另一些错误 $F_2(i)$ 。另外，每个补丁都耗费一定的时间。

试设计一个算法，利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。

输入数据

文件第 $1$ 行有 $2$ 个正整数 $n$ 和 $m$ ， $n$ 表示错误总数， $m$ 表示补丁总数。接下来 $m$ 行给出了 $m$ 个补丁的信息。每行包括一个正整数，表示运行补丁程序 $i$ 所需时间，以及 $2$ 个长度为 $n$ 的字符串，中间用一个空格符隔开。

第 $1$ 个字符串中，如果第 $k$ 个字符 $b_k$ 为+，则表示第 $k$ 个错误属于 $B_1(i)$ 。若为-，则表示第 $k$ 个错误属于 $B_2(i)$ ，若为0，则第 $k$ 个错误既不属于 $B_1(i)$ 也不属于 $B_2(i)$ ，即软件中是否包含第 $k$ 个错误并不影响补丁 $i$ 的可用性。
第 $2$ 个字符串中，如果第 $k$ 个字符 $b_k$ 为+，则表示第 $k$ 个错误属于 $F_1(i)$ ，若为-，则表示第 $k$ 个错误属于 $F_2(i)$ ，若为0，则第 $k$ 个错误既不属于 $F_1(i)$ 也不属于 $F_2(i)$ ，即软件中是否包含第 $k$ 个错误不会因使用补丁 $i$ 而改变。

输出数据

输出最小耗时，如果问题无解，则输出 $0$ 。

样例输入

复制

3 3
1 000 00-
1 00- 0-+
2 0-- -++ · \n
 ·   ·   \n
 ·   ·   \n
 ·   ·   \n

样例输出

复制

8 \n

样例说明

$\leq n \leq 20, 1 \leq m \leq 100$

提交

请先登录

提交

Source

LibreOJ