UVa-658, Live Archive-5629, TJU-1606, POJ-1482, ZOJ-1192: It's not a Bug, it's a Feature!

問題概要

N(<20)個のソフトとM(<100)個のバッチがある。各バッチは、適用にかかる時間と、適用できる条件、適用した後に消去、発生するバグなどの情報を持っている。全てのバグを消すのに必要な時間を最小化する問題。

解法

各ソフトが今バグを含んでいるかどうかを状態にしてビットDP。バッチが適用できるか、バッチ適用後にどういう状態になるかは適切に前処理をして高速に判定できるようにしておく。計算量はちょっとギリギリ。

acceptされたコード

計算量O(2^N * M * N)。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 20;
const int MAX_M = 100;
const int INF = 1<<29;

struct patch{
	int time, can_apply_mask, can_apply, fix_and, fix_or;
};

struct state{
	int bugs, dist;
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

int N, M;
patch patches[MAX_M];
int dist[1<<MAX_N];

void init(){
	for(int k=0; k<M; k++){
		char buf1[MAX_N + 1], buf2[MAX_N + 1];
		int t, can_apply_mask=0, can_apply=0, fix_and=(1<<N)-1, fix_or=0;
		scanf(" %d %s %s ", &t, buf1, buf2);
		for(int i=0; i<N; i++){
			if(buf1[i] != '0'){
				can_apply_mask |= 1<<i;
			}

			if(buf1[i] == '+'){
				can_apply |= 1<<i;
			}
		}

		for(int i=0; i<N; i++){
			if(buf2[i] == '+'){
				fix_or |= 1<<i;
			}
			if(buf2[i] == '-'){
				fix_and &= ~(1<<i);
			}
		}

		patches[k] = (patch){t, can_apply_mask, can_apply, fix_and, fix_or};
	}
}

int solve(){
	fill(dist, dist+(1<<N), INF);
	priority_queue<state> que;
	que.push( (state){(1<<N)-1, 0} );
	dist[(1<<N)-1] = 0;

	while(!que.empty()){
		state tp = que.top(); que.pop();
		int bugs = tp.bugs, d = tp.dist;
		if(dist[bugs] < d) continue;
		if(bugs == 0){
			return dist[bugs];
		}

		for(int i=0; i<M; i++){
			const patch& p = patches[i];
			if( (bugs & p.can_apply_mask) == p.can_apply ){
				int nd = d + p.time;
				int nbug = (bugs & p.fix_and) | p.fix_or;
				if(nd < dist[nbug]){
					dist[nbug] = nd;
					que.push( (state){nbug, nd} );
				}
			}
		}
	}

	return -1;
}

int main(){
	int c = 0;
	while(scanf(" %d %d ", &N, &M), N){
		printf("Product %d\n", ++c);
		init();
		int ans = solve();
		if(ans == -1){
			puts("Bugs cannot be fixed.");
		}
		else{
			printf("Fastest sequence takes %d seconds.\n", ans);
		}
		puts("");
	}

	return 0;
}