UVa 658 It's not a Bug, it's a Feature! (状态压缩+Dijstra)

题意：首先给出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不可能被完全消除那么就输出。

析：我们首先对所有的状态进行压缩，然后对每个状态进行搜索，使用最短路，最后并对状态进行判断能不能进行打补丁，最后看

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#include <sstream>

#define debug() puts("++++");

#define gcd(a, b) __gcd(a, b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-5;

const int maxn = 1e6 + 10;

const int mod = 1e6;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline bool is_in(int r, int c){

  return r >= 0 && r < n && c >= 0 && c < m;

}

struct Patch{

  int bm, bp;

  int am, ap;

  int t;

};

Patch a[110];

char s1[25], s2[25];

int d[1<<20];

void print(int j){

  for(int i = 0; i < n; ++i)

    if(j & (1<<i))  putchar('1');

    else putchar('0');

}

int dijstra(int s){

  priority_queue<P, vector<P>, greater<P> > pq;

  pq.push(P(0, s));

  fill(d, d+(1<<20), INF);

  d[s] = 0;

  while(!pq.empty()){

    P p = pq.top();  pq.pop();

    if(p.second == 0)  return p.first;

    int v = p.second;

    if(d[v] < p.first)  continue;

    for(int i = 0; i < m; ++i){

      if(((p.second & a[i].bp) == a[i].bp) && ((p.second & a[i].bm) == 0)){

        int u = (p.second | a[i].ap) & a[i].am;

        if(d[u] > d[v] + a[i].t){

          d[u] = d[v] + a[i].t;

          pq.push(P(d[u], u));

        }

      }

    }

  }

  return -1;

}

int main(){

  int kase = 0;

  while(scanf("%d %d", &n, &m) && m+n){

    memset(a, 0, sizeof a);

    for(int i = 0; i < m; ++i){

      scanf("%d", &a[i].t);

      scanf("%s", s1);

      scanf("%s", s2);

      a[i].am = (1<<n)-1;

      for(int j = 0; j < n; ++j){

        if(s1[j] == '+')  a[i].bp |= (1<<j);

        else if(s1[j] == '-')  a[i].bm |= (1<<j);

        if(s2[j] == '+')  a[i].ap |= (1<<j);

        else if(s2[j] == '-')  a[i].am ^= (1<<j);

      }

    }

    int ans = dijstra((1<<n)-1);

    printf("Product %d\n", ++kase);

    if(ans == -1)  printf("Bugs cannot be fixed.");

    else  printf("Fastest sequence takes %d seconds.", ans);

    puts("\n");

  }

  return 0;

}

是不是能完全打完所有的补丁，

由于是要时间是最少，所以我们可以用优先队列进行维护。

代码如下：

巴特西

UVa 658 It's not a Bug, it's a Feature! (状态压缩+Dijstra)

最新文章

热门文章