当前位置：首页 > news >正文

It's not a Bug, It's a Feature! --POJ 1482

news 来源：原创 2024/5/20 21:39:18

1、题目类型：BFS、位运算、优先队列。

2、解题思路：深度搜索。题意，维修一台有病毒的电脑，有 n 种病毒、m 种补丁包，每种补丁包必需以基于当前电脑的某些条件（如必需在电脑上面存在某种病毒、不存在某种病毒等等），在满足当前条件的情况下，补丁包可以消除某些病毒，但同时也可能产生新的病毒。要求找出删除所有病毒的最短时间。步骤，（1）将给出的补丁包信息记录在结构体 Pragram 中；（2)当前电脑的所用时间、病毒状态用结构体Node 型记录下来，由于其病毒数目小于20，所以可以用 int 类型的各位标示（“+ ”表示为0、“-”表示为1；（3）BFS搜索满足补丁状态条件的Node进入优先队列，优先队列按照其用时排序，这样又有利于寻找最短时间，直到找到结果状态输出，否则补丁包更新不成功。

3、注意事项：注意优先队列priority_queue的重载；check()判断状态条件中注意“0” 即无关的条件处理。

4、实现方法:

#include < iostream >
#include < queue >
using namespace std;

struct Pragram
{
int time;
char start[ 21 ],end[ 21 ];
};

struct Node
{
int t,state;
bool operator < ( const Node A) const
{
return t > A.t;
}
};

Pragram P[ 101 ];
int n,m,flag,ans;
int vis[ 1148576 ];

// k 表示第k个补丁、state表示当前状态、&val 表示补丁后状态
bool Check( int k, int state, int & val)
{
int i,cnt0 = 0 ,cnt1 = 0 ;
for (i = 0 ;i < n;i ++ )
{
if (P[k].start[i] != ' 0 ' )
{
if (P[k].start[i] == ' + ' )
{
if ((state & ( 1 << i)))
return false ;
}
else
{
if ((state & ( 1 << i)) == 0 )
return false ;
}
}
}
val = 0 ;
for (i = 0 ;i < n;i ++ )
{
if (P[k].end[i] == ' 0 ' )
{
if (state & ( 1 << i))
{
val ^= ( 1 << i);
}
}
else if (P[k].end[i] == ' - ' )
{
val ^= ( 1 << i);
}
}
return true ;
}

// + 表示为0、-表示为1
void BFS( int ca)
{
int i;
flag = 0 ,ans = 10000000 ; // 初始化标示变量
priority_queue < Node > Q;
Node tmp;
tmp.state = 0 ;
tmp.t = 0 ;
Q.push(tmp);
vis[ 0 ] = 1 ;
while ( ! Q.empty())
{
tmp = Q.top();
Q.pop();
if (tmp.t > ans)
break ;
if (tmp.state == (( 1 << n) - 1 )) // 终止状态
{
cout << " Product " << ca << endl;
cout << " Fastest sequence takes " << tmp.t << " seconds. " << endl << endl;
return ;
}
for (i = 0 ;i < m;i ++ )
{
int Estate;
if (Check(i,tmp.state,Estate))
{
if ( ! vis[Estate])
{
Node N;
N.state = Estate;
N.t = tmp.t + P[i].time;
Q.push(N);
vis[Estate] = N.t;
}
else if (vis[Estate] > (tmp.t + P[i].time))
{
Node N;
N.state = Estate;
N.t = tmp.t + P[i].time;
Q.push(N);
vis[Estate] = N.t;
}
}
}
}
if ( ! flag)
{
cout << " Product " << ca << endl;
cout << " Bugs cannot be fixed. " << endl << endl;
}
else
{
cout << " Product " << ca << endl;
cout << " Fastest sequence takes " << ans << " seconds. " << endl << endl;
}
}

int main()
{
int i,ca = 1 ;
while (cin >> n >> m)
{
if (n == 0 && m == 0 )
break ;
memset(vis, 0 , sizeof (vis));
for (i = 0 ;i < m;i ++ )
{
cin >> P[i].time >> P[i].start >> P[i].end;
}
BFS(ca ++ );
}
return 0 ;
}

转载于:https://www.cnblogs.com/yongze103/archive/2010/10/18/1854002.html