首页 > 代码库 > POJ 1482 It's not a Bug, It's a Feature! 状压+spfa

POJ 1482 It's not a Bug, It's a Feature! 状压+spfa

2024-07-16 23:10:21   233人阅读

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 }

 


联系
我们