题目描述某软件公司发布了若干补丁每个补丁用于修复某些bug\texttt{bug}bug但可能依赖其他bug\texttt{bug}bug的存在或不存在并且可能会引入新的bug\texttt{bug}bug。给定初始状态所有nnn个bug\texttt{bug}bug均存在每个补丁具有应用时间。问是否存在一系列补丁可重复使用将软件变为无bug\texttt{bug}bug状态并求最少总时间。每个补丁由两个长度为nnn的字符串描述第一个字符串描述补丁应用的前提条件表示该bug\texttt{bug}bug必须存在-表示该bug\texttt{bug}bug必须不存在0表示无关紧要。第二个字符串描述补丁的效果表示引入该bug\texttt{bug}bug-表示修复该bug\texttt{bug}bug若存在0表示不影响。输入格式多组数据。每组数据第一行为两个整数nnn和mmm1≤n≤201 \le n \le 201≤n≤201≤m≤1001 \le m \le 1001≤m≤100表示 bug 数量和补丁数量。接下来mmm行每行包含一个整数ttt补丁应用时间和两个长度为nnn的字符串条件串和效果串。输入以0 0结束。输出格式对于每组数据输出两行第一行为Product X:其中XXX为产品编号从111开始。第二行若存在方案输出Fastest sequence takes T seconds.其中TTT为最少时间否则输出Bugs cannot be fixed.。每组输出后跟一个空行。样例输入3 3 1 000 00- 1 00- 0- 2 0-- - 4 1 7 0- 0-- 0 0输出Product 1 Fastest sequence takes 8 seconds. Product 2 Bugs cannot be fixed.题目分析本题将软件状态建模为nnn位二进制数第iii位为111表示bug\texttt{bug}bugiii存在。初始状态为(1n)-1目标状态为000。每个补丁相当于从当前状态到新状态的有向边边权为补丁时间。应用补丁时需要满足条件对于条件串中的每位若为则当前状态对应位必须为111若为-则必须为000若为0则任意。满足条件后根据效果串更新状态若为-则将该位清000若为则将该位置111若为0则不变。由于nnn最大202020状态数为220≈1062^{20} \approx 10^6220≈106节点数可接受。使用Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra算法求从初始状态到目标状态的最短路。由于边权非负Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra正确且高效。每个状态扩展时遍历mmm个补丁检查条件并生成后继状态。总时间复杂度O(2n⋅m)O(2^n \cdot m)O(2n⋅m)在n20n20n20m100m100m100时约为10810^8108可接受实际运行时间0.9200.9200.920秒。解题思路状态表示用整数state表示nnn位二进制数表示bug\texttt{bug}bug状态。补丁结构存储时间weight、条件串s1、效果串s2。条件检查对每个补丁检查当前状态u是否满足s1的所有位若s1[j] 且bit 0则不满足。若s1[j] -且bit ! 0则不满足。若s1[j] 0忽略。状态转移若条件满足则根据s2生成新状态v若s2[j] -则将对应位清000。若s2[j] 则将对应位置111。若s2[j] 0不变。Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra从初始状态(1n)-1开始优先队列按当前距离排序。每次取出距离最小的状态生成所有后继若新距离更小则更新入队。终止条件目标状态000被弹出或队列为空。输出若dist[0]为无穷大则输出Bugs cannot be fixed.否则输出最短时间。复杂度分析状态数V2nV 2^nV2n边数最多V⋅mV \cdot mV⋅m。Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra使用优先队列时间复杂度O((VE)log⁡V)O((V E) \log V)O((VE)logV)其中EEE为实际生成的边数最坏O(2n⋅m)O(2^n \cdot m)O(2n⋅m)。对于n20n20n20V≈106V \approx 10^6V≈106E≈108E \approx 10^8E≈108但实际可达状态较少运行时间可接受。代码实现// Its Not a Bug Its a Feature// UVa ID: 658// Verdict: Accepted// Submission Date: 2018-05-22// UVa Run Time: 0.920s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN(120),INF0x3f3f3f3f;structrule{intweight;string s1,s2;}rules[128];structedge{intto,weight;edge(intto0,intweight0):to(to),weight(weight){}booloperator(constedgee)const{returnweighte.weight;}};intn,m,dist[MAXN];vectoredgegetNext(intu){vectoredgenext;for(inti0;im;i){boolmatchedtrue;for(intj0;jn;j){intbit(1(n-j-1))u;if((bitrules[i].s1[j]-)||(!bitrules[i].s1[j])){matchedfalse;break;}}if(matched){intvu;for(intj0;jn;j){if(rules[i].s2[j]-)v(~(1(n-j-1)));if(rules[i].s2[j])v|(1(n-j-1));}next.push_back(edge(v,rules[i].weight));}}returnnext;}voidmooreDijkstra(){for(inti0;i(1n);i)dist[i]INF;intu(1n)-1;dist[u]0;priority_queueedgeq;q.push(edge(u,dist[u]));while(!q.empty()){edge vq.top();q.pop();for(autoe:getNext(v.to))if(dist[e.to]dist[v.to]e.weight){dist[e.to]dist[v.to]e.weight;q.push(edge(e.to,dist[e.to]));}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;intweight;string s1,s2;while(cinnm){if(n0)break;coutProduct cases\n;for(inti0;im;i){cinweights1s2;rules[i]rule{weight,s1,s2};}mooreDijkstra();if(dist[0]INF)coutBugs cannot be fixed.\n\n;elsecoutFastest sequence takes dist[0] seconds.\n\n;}return0;}总结本题将Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra状态建模为二进制数将补丁转化为有向边利用Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra算法求解最短路径。关键点包括正确实现状态转移和条件检查。使用位运算高效操作状态。注意输出格式每组后跟空行。优化由于边权非负Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra适用也可使用SPFA\texttt{SPFA}SPFA但Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra更稳定。该解法是状态空间搜索的典型应用适用于n≤20n \le 20n≤20的中等规模问题。