UVA 658 It's not a Bug, it's a Feature!
2024-10-19 03:34:32
这个题目巧妙之处在于用二进制的每个位1,0分别表示bug的有无,以及实施补丁对相应bug的要求以及实施后的对bug的影响。
软件bug的状态:1表示相应bug仍然存在,0表示已经修复。这样可以将软件的状态用一个整数表示,例如1100(12)表示第1,2个bug存在,后面两个已经修复。
那么,对于n个bug 的软件,起点src = (1<<n)-1表示软件初始状态 111....111,终点sink = 0表示软件已经修复。
实施补丁的条件:
+-0 表示实施该补丁需要第1个bug存在,第2个bug不存在,对第三个无要求,可以用两个整数a1,a2表示,其中a1表示需要哪些bug存在,也就是对应字符串为'+'的地方,该整数的二进制位设为1,
其他位为0,这里为a1 = 100;a2表示哪些bug不能存在,对于字符串中'-'的位置a2相应二进制位设为0,其余为1,a2 = 101。这样判断某个软件当前状态(用整数x表示)是否符合实施补丁要求可以这样判断:
(x | a1) == x && (x & a2 )==x
补丁对bug的影响:
同样用两个整数b1,b2,表示方式和前面a1,a2一样,b1同a1,即'+'位设为1,其余为0;b2同a2,非'-'都设为1,'-'设为0。对于x实施补丁的过程就变成了:y = x,y |= b1,y &= b2.这样由状态x变成了y。
因此每个状态转化为一个整数,整个问题变成球一条从src,到sink的最短路,每条路的长度就是每个补丁花费的时间,dij可破之。
代码:
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pb push_back
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<int>:: iterator IT;
typedef pair<int, int> pii;
#define N 30
#define M 200
#define MAX 10000000
char a[N], b[N];
int s[M][], t[M][], w[M];
int d[MAX], inq[MAX];
int n, m, src, sink;
priority_queue<pii, vector<pii>, greater<pii> > q;
void dij(void)
{
memset(d, 0x0f, sizeof(d));
// memset(inq, 0, sizeof(inq));
d[src] = ;
// inq[src] = 1;
q.push(make_pair(d[src], src));
while(!q.empty())
{
pii u = q.top();
q.pop();
int x = u.second;
if(d[x] != u.first)
continue;
for(int i = ; i < m; i++)
{
if(((x | s[i][]) == x) && ((x & s[i][]) == x))
{
int y = x;
y |= t[i][];
y &= t[i][];
if(d[x] + w[i] < d[y])
{
d[y] = d[x] + w[i];
q.push(make_pair(d[y],y));
}
}
}
}
}
int main(void)
{
int T = ;
while(scanf("%d%d", &n, &m),n+m)
{
memset(s, , sizeof(s));
memset(t, , sizeof(t));
src = (<<n) - ;
sink = ;
for(int i = ; i < m; i++)
{
scanf("%d%s%s", &w[i], a, b);
for(int j = ; j < n; j++)
{
if(a[j] == '+')
s[i][] |= (<<j);
if(a[j] != '-')
s[i][] |= (<<j);
if(b[j] == '+')
t[i][] |= (<<j);
if(b[j] != '-')
t[i][] |= (<<j);
}
}
dij();
printf("Product %d\n", T++);
if(d[] < inf)
printf("Fastest sequence takes %d seconds.\n", d[]);
else
puts("Bugs cannot be fixed.");
puts("");
}
return ;
}
最新文章
- RecyclerView的使用(二)
- C++设计模式-策略模式(2)
- 【UWP】批量修改图标尺寸
- mysql查询所有表行数
- zoj3822 Domination(概率dp)
- 学习JQuery中文文档之map()函数和get()函数
- 编译并使用Lua语言
- Windows 下Python操作MySQL
- 说说JSON和JSONP,浅析JSONP解决AJAX跨域问题
- FPGA计算3行同列数据之和
- jquery closest &; parent比较
- mysql-innodb的事务日志
- bzoj2595: [Wc2008]游览计划 斯坦纳树
- Cloudera Manager安装之Cloudera Manager安装前准备(CentOS6.5)(一)
- xml布局内容总结(一)--Android
- 嵌入式Linux之我行——ARM MMU工作原理剖析【转】
- object类型转换为Array类型
- E20181030-hm
- NHibernate之旅(8):巧用组件之依赖对象
- Fragmen直接来回切换deno
热门文章
- HDFS之SequenceFile和MapFile
- Linux的僵尸进程产生原因及解决方法
- [.Net MVC] 使用 log4net 日志框架
- [leetcode] 407. Trapping Rain Water II
- hdu 5055 Bob and math problem
- new static() 和 new self() 的区别异同
- grunt学习
- table隔行换色
- 对WebClient扩展自动解压缩页面
- mirantis fuel puppet执行顺序 和 对整个项目代码的执行流程理解