文档章节

【刷题】LOJ 6009 「网络流 24 题」软件补丁

o
 osc_1ee7cxmx
发布于 2018/08/06 21:01
字数 1070
阅读 0
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

题目描述

某公司发现其研制的一个软件中有 $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-- -++

样例输出

8

数据范围与提示

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

题解

不知道这题为什么在网络流24题里

状压SPFA,设 $f[i]$ 代表所有补丁达到 $i$ 状态最少需要的步数

跑SPFA,状态改变可以自己推一下位运算的式子

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=20+2,MAXM=100+10,inf=0x3f3f3f3f;
int n,m,cnt,f[1<<MAXN],was[MAXM],nd[MAXM],hv[MAXM],ad[MAXM],rd[MAXM],ps[MAXM],p[1<<MAXN];
char B[MAXM][MAXN],F[MAXM][MAXN];
std::queue<int> q;
template<typename T> inline void read(T &x)
{
    T data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void init()
{
    for(register int i=1;i<=m;++i)
        for(register int j=0;j<n;++j)
        {
            if(B[i][j]=='+')nd[i]|=(1<<n-j-1);
            if(B[i][j]=='0')hv[i]|=(1<<n-j-1);
            if(F[i][j]=='+')ad[i]|=(1<<n-j-1);
            if(F[i][j]=='-')rd[i]|=(1<<n-j-1);
            if(F[i][j]=='0')ps[i]|=(1<<n-j-1);
        }
}
int main()
{
    read(n);read(m);
    for(register int i=1;i<=m;++i)read(was[i]),scanf("%s",B[i]),scanf("%s",F[i]);
    init();
    memset(f,inf,sizeof(f));
    f[(1<<n)-1]=0;
    p[(1<<n)-1]=1;
    q.push((1<<n)-1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        p[x]=0;
        for(register int i=1;i<=m;++i)
            if((hv[i]&x|nd[i])!=x)continue;
            else
            {
                int nxt=(x&ps[i])|(x|ad[i])&(~rd[i]);
                if(f[nxt]>f[x]+was[i])
                {
                    f[nxt]=f[x]+was[i];
                    if(!p[nxt])p[nxt]=1,q.push(nxt);
                }
            }
    }
    write(f[0]==inf?0:f[0],'\n');
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

java架构师成长路线-高并发网络编程的分类

鲁班学院java架构师成长路线 随着互联网时代的到来,高并发网络编程这一新鲜名词早已跃然于纸上,为了满足大众眼光的需求,我为大家找了些关于高并发网络编程方面的资料,本文便来介绍高并发...

osc_o494ayqf
19分钟前
5
0
python dict乱码如何解决

定义字典并直接输出,结果输出结果中文是乱码展示 d={'name':'lily','age':18,'sex':'女','no':1121}print d 输出结果: {'age': 18, 'no': 1121, 'name': 'lily', 'sex': '\xe5\xa5\xb3'}...

osc_9mjo6c4e
20分钟前
14
0
硬肝50天,18w字的实战编程资料《重学Java设计模式》终于 出炉了

沉淀、分享、成长,让自己和他人都能有所收获! 一、前言 作者从5月20日那天投身实战型设计模式打磨,通过模拟互联网业务开发实际需求作为学习场景,讲解设计模式。 全书共计22个真实业务场景...

osc_zls6dx9i
22分钟前
20
0
怎么才能让Spring AOP有最大的作用--乐字节java

Spring AOP 日志处理带来的问题 我们有一个Pay(接口) 然后两个实现类DollarPay和RmbPay,都需要重写pay()方法, 这时我们需要对pay方法进行性能监控,日志的添加等等怎么做? 最容易想到的方法...

osc_sb30h1xb
24分钟前
14
0
Python 实现将numpy中的nan和inf,nan替换成对应的均值

nan:not a number inf:infinity;正无穷 numpy中的nan和inf都是float类型 t!=t 返回bool类型的数组(矩阵) np.count_nonzero() 返回的是数组中的非0元素个数;true的个数。 np.isnan() 返回b...

osc_sfl7wfr9
26分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部