poj1482（隱式圖求最短路）
來源：程序員人生 發布時間：2014-12-08 08:41:38 閱讀次數：2888次
題目鏈接
題意：補釘在修正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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
