poj1482（隐式图求最短路）
来源：程序员人生 发布时间：2014-12-08 08:41:38 阅读次数：2732次
题目链接
题意：补钉在修正bug时，有时也会引入新的bug。假定有n个潜伏的bug m个补钉，每一个补钉用两个长度为n的字符串表示，其中字符串的每一个位置表示1个bug，第1个串表示打补钉之前的状态('-'表示该bug必须不存在，’+‘表示必须存在，0表示无所谓，第2个串表示打补钉以后的状态(-'表示不存在，’+‘表示存在，0表示不变)。每一个补钉都有1个履行时间，你的任务使用最少的时间把1个bug都存在的软件通过打补钉的方式变得没有bug。1个补钉可以打屡次。
解法：状压表示每一个补钉的存在与否。隐式搜索，会有很多状态根本搜不到，spfa直接搜索便可。对每次都枚举使用所有的补钉修补并松弛得到的状态。
代码：
/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;
#define eps 1e⑻
#define zero(_) (abs(_)<=eps)
const double pi=acos(⑴.0);
typedef long long LL;
const int Max=10100000;
const LL INF=0x3FFFFFFF;
int state[(1<<20)+10];
int n,m;
struct bug
{
int cost;
char start[22];
char end[22];
} bugs[1200];
bool operator<(const bug& a,const bug& b)
{
return a.cost<b.cost;
}
int que[Max];
bool rem[(1<<20)+10];
int getstate(int st,int j)
{
for(int i=0; i<n; i++)
{
if(bugs[j].start[i]=='-'&&(st&(1<<i)))
return ⑴;
if(bugs[j].start[i]=='+'&&!(st&(1<<i)))
return ⑴;
}
int re=0;
for(int i=0; i<n; i++)
{
if(bugs[j].end[i]=='+')
re|=(1<<i);
if(bugs[j].end[i]=='0')
re|=st&(1<<i);
}
return re;
}
int main()
{
int kk=1;
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
for(int i=0; i<m; i++)
scanf("%d%s%s",&bugs[i].cost,bugs[i].start,bugs[i].end);
sort(bugs,bugs+m);
memset(state,⑴,sizeof state);
memset(rem,0,sizeof rem);
state[(1<<n)⑴]=0;
rem[(1<<n)⑴]=1;
int left=0,right=1;
que[0]=(1<<n)⑴;
while(left<right)
{
//cout<<left<<endl;
int t=que[left++];
for(int i=0; i<m; i++)
{
int st=getstate(t,i);
if(st!=⑴&&(state[st]==⑴||state[st]>state[t]+bugs[i].cost))
{
state[st]=state[t]+bugs[i].cost;
if(!rem[st])
que[right++]=st,rem[st]=1;
}
}
rem[t]=0;
}
printf("Product %d
",kk++);
if(state[0]==⑴)
puts("Bugs cannot be fixed.");
else
{
printf("Fastest sequence takes %d seconds.
",state[0]);
}
cout<<endl;
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
