poj1482（隱式圖求最短路）
來源：程序員人生 發(fā)布時間：2014-12-08 08:41:38 閱讀次數(shù)：2882次
題目鏈接
題意：補(bǔ)釘在修正bug時，有時也會引入新的bug。假定有n個潛伏的bug m個補(bǔ)釘，每一個補(bǔ)釘用兩個長度為n的字符串表示，其中字符串的每一個位置表示1個bug，第1個串表示打補(bǔ)釘之前的狀態(tài)('-'表示該bug必須不存在，’+‘表示必須存在，0表示無所謂，第2個串表示打補(bǔ)釘以后的狀態(tài)(-'表示不存在，’+‘表示存在，0表示不變)。每一個補(bǔ)釘都有1個履行時間，你的任務(wù)使用最少的時間把1個bug都存在的軟件通過打補(bǔ)釘?shù)姆绞阶兊脹]有bug。1個補(bǔ)釘可以打?qū)掖巍?/span>
解法：狀壓表示每一個補(bǔ)釘?shù)拇嬖谂c否。隱式搜索，會有很多狀態(tài)根本搜不到，spfa直接搜索便可。對每次都枚舉使用所有的補(bǔ)釘修補(bǔ)并松弛得到的狀態(tài)。
代碼：
/******************************************************
* @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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
