P2761 软件补丁问题

    • 451通过
    • 1.2K提交
  • 题目提供者 yyy2015c01 管理员
  • 评测方式 云端评测
  • 标签 网络流 网络流24题 O2优化
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    none!

    题目描述

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

    换句话说,对于每一个补丁 i,都有 2 个与之相应的错误集合 B1[i]和 B2[i],使得仅当软件包含 B1[i]中的所有错误,而不包含 B2[i]中的任何错误时,才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i],而同时加入另一些错误 F2[i]。另外,每个补丁都耗费一定的时间。

    试设计一个算法,利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。对于给定的 n 个错误和 m 个补丁程序,找到总耗时最少的软件修复方案。

    输入输出格式

    输入格式:

    第 1 行有 2 个正整数 n 和 m,n 表示错误总数,m表示补丁总数,1<=n<=20, 1<=m<=100。

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

    第 1 个字符串中,如果第 k 个字符 bk 为“+”,则表示第 k 个错误属于 B1[i],若为“-”,则表示第 k 个错误属于 B21[i],若为“0”,则第 k 个错误既不属于 B1[i]也不属于 B2[i],即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。

    第 2 个字符串中,如果第 k 个字符 bk为“-”,则表示第 k 个错误属于 F1[i],若为“+”,则表示第 k 个错误属于 F2[i],若为“0”,则第 k 个错误既不属于 F1[i]也不属于 F2[i],即软件中是否包含第 k 个错误不会因使用补丁i 而改变。

    输出格式:

    程序运行结束时,将总耗时数输出。如果问题无解,则输出 0。

    输入输出样例

    输入样例#1: 复制
    3 3
    1 000 00-
    1 00- 0-+
    2 0-- -++
    
    输出样例#1: 复制
    8

    说明

    none!

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。