[题解]UVA658 It's not a Bug, it's a Feature!

链接：http://vjudge.net/problem/viewProblem.action?id=22169

描述：有n个漏洞，m个修复漏洞的方法，每种方法耗时不一样，求修复漏洞的最短时间。每种方法的使用对当前漏洞分布的状态有要求，符合要求才能修复，并有可能引入新漏洞。

思路：单源点最短路

这道题卡了我很久，因为不知道怎么表示状态。最开始受到'0'的影响，觉得必须要三进制，于是写得很麻烦还错了。之后觉得可以用二进制分别存储'+'和'-'的状态。我定义两个数组，Condition[i][0]表示第i个方法'+'要满足的条件，Condition[i][1]表示第i个方法'-'要满足的条件；Operate[i][0]和Operate[i][1]同理表示修复手段。

判断当前状态Cur是否可以用第i个方法：（可以自己举个例子推一下）

Cur&Condition[i][0])==Condition[i][0]

((~Cur)&Condition[i][1])==Condition[i][1]

用第i个方法修复漏洞：

Cur|=Operate[i][0];

Cur&=(~Operate[i][1]);

然后的问题就是，状态量太多了，或者说是无效的状态量太多了，怎么解决存储问题呢？这个时候我们就考虑不存边，在搜索的时候按照判断结果走，相当于是动态找状态。然后一个bfs就解决问题了。

我的实现：

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <queue>

 5 using namespace std;

 6 #define MaxM 120

 7 #define MaxN 30

 8 int Cost[MaxM],Condition[MaxM][5],Operate[MaxM][5];

 9 char s1[MaxN],s2[MaxN];

10 bool vis[(1<<20)+20];

11 int n,m,ans;

12 bool Sol;

13 typedef pair<int, int> p;

14 struct cmp

15 {

16     bool operator()(p a,p b)

17     {

18         return a.first>b.first;

19     }

20 };

21 priority_queue <p, vector<p>, cmp> q;

22 inline void Clean()

23 {

24     memset(Condition,0,sizeof(Condition));

25     memset(Operate,0,sizeof(Operate));

26     Sol=false;

27     memset(vis,false,sizeof(vis));

28     while(!q.empty())

29         q.pop();

30 }

31 void Bfs()

32 {

33     q.push(make_pair(0,(1<<n)-1));

34     p u;

35     int i,fi,Cur;

36     while(!q.empty())

37     {

38         u=q.top();q.pop();

39         fi=u.first;Cur=u.second;

40         if(!Cur)

41         {

42             Sol=true;

43             ans=fi;

44             return;

45         }

46         if(vis[Cur])

47             continue;

48         vis[Cur]=true;

49         for(i=1;i<=m;++i)

50         {

51             Cur=u.second;

52             if((Cur&Condition[i][0])==Condition[i][0]&&((~Cur)&Condition[i][1])==Condition[i][1])

53             {

54                 Cur|=Operate[i][0];

55                 Cur&=(~Operate[i][1]);

56                 q.push(make_pair(fi+Cost[i],Cur));

57             }

58         }

59     }

60 }

61 int main()

62 {

63     int i,j,t;

64     for(t=1;;t++)

65     {

66         Clean();

67         scanf("%d%d",&n,&m);

68         if(n==0&&m==0)

69             break;

70         for(i=1;i<=m;++i)

71         {

72             scanf("%d%s%s",&Cost[i],s1,s2);

73             for(j=0;j<n;++j)

74             {

75                 if(s1[j]=='+')

76                     Condition[i][0]|=(1<<j);

77                 else if(s1[j]=='-')

78                     Condition[i][1]|=(1<<j);

79             }

80             for(j=0;j<n;++j)

81             {

82                 if(s2[j]=='+')

83                     Operate[i][0]|=(1<<j);

84                 else if(s2[j]=='-')

85                     Operate[i][1]|=(1<<j);

86             }

87         }

88         Bfs();

89         printf("Product %d\n",t);

90         if(Sol)

91             printf("Fastest sequence takes %d seconds.\n\n",ans);

92         else

93             printf("Bugs cannot be fixed.\n\n");

94     }

95     return 0;

96 }

巴特西

[题解]UVA658 It's not a Bug, it's a Feature!

最新文章

热门文章