UVA658，隐式图+最短路+二进制子集枚举

题目：

首先给出n和m，表示有n个bug和m个补丁。一开始存在n个bug，用1表示一个bug存在0表示不存在，所以一开始就是n个1，我们的目的是要消除所有的bug，所以目标状态就是n个0。对于每个补丁，会给出使用这个补丁的时间，另外会给出两个长度为n的字符串，第一个字符串表示这个补丁适用于什么情况下的bug，第二个字符串表示使用完这个补丁后原来的bug会变成怎么样。先说第一个字符串，s[i]=’0’，表示第i个bug存在与否都无所谓；s[i]=’+’，表示第i个bug一定要存在；s[i]=’-‘，表示第i个bug必须不存在；能不能使用这个补丁，就要看当前bug的状态是不是能不能全部满足第一个字符串，能的话就可以使用。第二个字符串表示使用完后的情况，ss[i]=’0’，表示第i个bug保持不变，原来是1就1是0就0；ss[i]=’+’，表示第i个bug必须为1；ss[i]=’-‘，表示第i个bug必须为0。

最终题目要求解的就是消除所有的bug并且用时最短，输出最短时间，如果bug不可能被完全消除那么就输出失败

思路：

可以看出是一个隐式图的最短路，但是因为可能在经过几个补丁后回到原本的状态，所以可能存在环，并不是DAG，所以动态规划无法解决，考虑使用Dijkstra或者SPFA：

第一次尝试：

需要考虑怎么来表示状态，因为最多只有二十个补丁，而且每个补丁存在与否的表示方法是‘-’或者‘+’，所以首先考虑string型字符串来储存每个状态。但是跑SPFA时候，数组d[maxn]，inq[maxn]等无法直接用字符串来表示下标，所以考虑给状态进行标号。用vectorstate 来保存当前所扩展出的所有状态，当扩展到一个新的状态v的时候，在state中查找，如果已经存在该状态直接用它的标号，否则将状态v加入state中并给它一个编号。代码如下

#include 
#include 
#include 
#include 
#include 
#include 

#include
#include
#include
using namespace std;struct Node {int bugs, dist;bool operator < (const Node& rhs) const {return dist > rhs.dist;}
};
const int maxn = 20;
const int maxm = 100 + 5;
const int INF = 1000000000;int n, m, t[maxm], dist[1< q;Node start;start.dist = 0;start.bugs = (1<

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=25;
const int maxm=100+5;
const int INF=2147483647;int tim[maxm];
char before[maxm][maxn],after[maxm][maxn];
int beg,gol,kase=0;
int n,m;
int d[1<q;q.push(s);d[s]=0;inq[s]=0;while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=0;id[u]+tim[i]){d[v]=d[u]+tim[i];if(!inq[v]){q.push(v);inq[v]=1;if(++cnt[v]>=(1<>tim[i];cin>>before[i]>>after[i];}beg=(1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！