UVa 658 It‘s Not a Bug It‘s a Feature-拓冰建站

题目描述

某软件公司发布了若干补丁，每个补丁用于修复某些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和mmm（1≤n≤201 \le n \le 201≤n≤20，1≤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存在。初始状态为(1<<n)-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)，在n=20n=20n=20，m=100m=100m=100时约为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：从初始状态(1<<n)-1开始，优先队列按当前距离排序。每次取出距离最小的状态，生成所有后继，若新距离更小则更新入队。终止条件：目标状态000被弹出，或队列为空。
输出：若dist[0]为无穷大，则输出"Bugs cannot be fixed."，否则输出最短时间。

复杂度分析

状态数V=2nV = 2^nV=2n，边数最多V⋅mV \cdot mV⋅m。
Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra使用优先队列，时间复杂度O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV)，其中EEE为实际生成的边数，最坏O(2n⋅m)O(2^n \cdot m)O(2n⋅m)。
对于n=20n=20n=20，V≈106V \approx 10^6V≈106，E≈108E \approx 10^8E≈108，但实际可达状态较少，运行时间可接受。

代码实现

// It's Not a Bug It's a Feature// UVa ID: 658// Verdict: Accepted// Submission Date: 2018-05-22// UVa Run Time: 0.920s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=(1<<20),INF=0x3f3f3f3f;structrule{intweight;string s1,s2;}rules[128];structedge{intto,weight;edge(intto=0,intweight=0):to(to),weight(weight){}booloperator<(constedge&e)const{returnweight>e.weight;}};intn,m,dist[MAXN];vector<edge>getNext(intu){vector<edge>next;for(inti=0;i<m;i++){boolmatched=true;for(intj=0;j<n;j++){intbit=(1<<(n-j-1))&u;if((bit&&rules[i].s1[j]=='-')||(!bit&&rules[i].s1[j]=='+')){matched=false;break;}}if(matched){intv=u;for(intj=0;j<n;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(inti=0;i<(1<<n);i++)dist[i]=INF;intu=(1<<n)-1;dist[u]=0;priority_queue<edge>q;q.push(edge(u,dist[u]));while(!q.empty()){edge v=q.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);intcases=0;intweight;string s1,s2;while(cin>>n>>m){if(n==0)break;cout<<"Product "<<++cases<<'\n';for(inti=0;i<m;i++){cin>>weight>>s1>>s2;rules[i]=rule{weight,s1,s2};}mooreDijkstra();if(dist[0]==INF)cout<<"Bugs cannot be fixed.\n\n";elsecout<<"Fastest 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更稳定。