首页 > 代码库 > POJ 1482 It's not a Bug, It's a Feature! 状压+spfa
POJ 1482 It's not a Bug, It's a Feature! 状压+spfa
http://poj.org/problem?id=1482
题意:先黑了一发程序猿,说软件总是有漏洞,然后打补丁拆了东墙补西墙。现在软件有不超过20个漏洞,有不超过100个补丁,每个补丁有运用条件(某些漏洞不能存在,某些漏洞必须存在)和作用效果(补漏洞,产生新漏洞),已经安装时间,开始有所有漏洞,问是否有一种安装补丁的顺序能填补所有漏洞,并求最短的时间。
分析:因为只有20个漏洞,所以可以状压,大概100万的级别,每位为0表示没有这个漏洞,为1表示有这个漏洞。记f[i]表示达到状态i所需最短时间,初始状态即 f[(1<<n)-1] = 0,目标状态为f[0]。
开始用dfs把序列里的0全部枚举成+-,然后连边spfa。。最后要么mle,要么wa,要么re。。直接连边,边数太大了。。实际上很多状态和边是没有必要的。具体怎么转移还是看程序吧。。
注意位运算优先级十分低,连比较运算符都低,所以尽量多加括号。
记忆化搜索貌似写不好会爆栈,然后网上还有的用bfs+堆过的。。仔细观察了一下貌似是spfa的“堆优化”,估计和上次slf优化一样,会被某些数据卡。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxq = (1<<20) + 10; 7 int q[(1<<20)+15]; 8 int n, m, maxn, oo, w[110]; 9 int f[(1<<20)+10], ha[(1<<20)+10];10 int cas = 0;11 char s1[30], s2[30];12 bool in[(1<<20)+10];13 int pre[110][2], fixed[110][2];14 void cook_the_raw(int i)15 {16 pre[i][0] = pre[i][1] = fixed[i][1] = 0;17 fixed[i][0] = maxn;18 for (int j = 0; j < n; j++){19 if (s1[j] == ‘+‘) pre[i][1] += 1 << j; //pre[i][1]某位为1表示patch[i]apply条件要求该漏洞20 else if (s1[j] == ‘-‘) pre[i][0] += 1 << j; //pre[i][0]某位为1表示patch[i]apply条件要求无该漏洞21 if (s2[j] == ‘+‘) fixed[i][1] += 1 << j; //fixed[i][1]某位为1表示apply后得到该漏洞22 else if (s2[j] == ‘-‘) fixed[i][0] -= 1 << j; //fixed[i][0]某位为0表示apply后修复该漏洞23 }24 }25 void init()26 {27 cas ++;28 maxn = (1 << n) - 1;29 f[maxn] = 0; ha[maxn] = cas;30 for (int i = 0; i < m; i++){31 scanf("%d %s %s", &w[i], s1, s2);32 cook_the_raw(i);33 }34 }35 void spfa()36 {37 int head, tail;38 head = tail = 0;39 q[tail++] = maxn;40 in[maxn] = true;41 while (head != tail)42 {43 int u = q[head++];44 if (head == maxq) head = 0;45 for (int i = 0; i < m; i++){46 if (((u & pre[i][1]) == pre[i][1]) && ((u & pre[i][0]) == 0)){ //满足patch[i]apply条件47 int v = (u | fixed[i][1]) & fixed[i][0]; //转移到的状态48 if (ha[v] != cas || f[v] > f[u] + w[i]){49 f[v] = f[u] + w[i]; ha[v] = cas;50 if (!in[v]){51 q[tail++] = v;52 if (tail == maxq) tail = 0;53 in[v] = true;54 }55 }56 }57 }58 in[u] = false;59 }60 }61 void print()62 {63 printf("Product %d\n", cas); 64 if (ha[0] != cas) printf("Bugs cannot be fixed.\n\n");65 else printf("Fastest sequence takes %d seconds.\n\n", f[0]);66 }67 int main()68 {69 memset(in, false, sizeof(in));70 memset(ha, 0, sizeof(ha));71 while(scanf("%d %d", &n, &m) && n+m)72 {73 init();74 spfa();75 print();76 }77 return 0;78 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。