AOJ 0247 - Arts and Crafts

問題文 : 図画工作

解法 :

$dp[i][j][k]$ : $i$ で表される道具の集合をを$j$ 日目に$k$ 個まで道具をかって実現することができるか, として事前にDP を行う.

それで, 袋から完成状態へDP の結果をコストとする辺を貼り, 流量を$N$ とした最小費用流を行う.

コード :

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cassert>
#include <vector>

using namespace std;

typedef pair<int, int> P;

struct edge {
	int to, cap, cost, rev;
};

int V;
vector<edge> G[50200];
int h[50200], dist[50200];
int prevv[50200], preve[50200];

void addEdge(int from, int to, int cap, int cost)
{
	V = max(V, max(from + 1, to + 1));
	G[from].push_back((edge){to, cap, cost, G[to].size()});
	G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});
}

int minCostFlow(int s, int t, int f)
{
	int res = 0;
	fill(h, h + V, 0);
	while (f > 0){
		priority_queue<P, vector<P>, greater<P> > pq;
		fill(dist, dist + V, 1000000000);
		dist[s] = 0; pq.push(P(0, s));
		while (!pq.empty()){
			P p = pq.top(); pq.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			for (int i = 0; i < G[v].size(); i++){
				edge &e = G[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					pq.push(P(dist[e.to], e.to));
				}
			}
		}
		
		if (dist[t] == 1000000000) return (-1);
		for (int v = 0; v < V; v++) h[v] += dist[v];
		
		int d = f;
		for (int v = t; v != s; v = prevv[v]){
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return (res);
}

int encode(int *p, int N)
{
	int ret = 0;
	for (int i = N - 1; i >= 0; i--)
		ret = ret * 3 + p[i];
	return (ret);
}

void decode(int bit, int N, int *p)
{
	for (int i = 0; i < N; i++){
		p[i] = bit % 3; bit /= 3;
	}
}

int main()
{
	int D, K, L;
	int M, N, P;
	int pow3[10];
	
	pow3[0] = 1;
	for (int i = 1; i <= 9; i++) pow3[i] = pow3[i - 1] * 3;
	
	while (scanf("%d %d %d", &D, &K, &L) && D){
		int c[8][8];
		for (int i = 0; i < D; i++)
			for (int j = 0; j < K; j++)
				scanf("%d", &c[i][j]);
		
		scanf("%d %d %d", &M, &N, &P);
		
		int tar[256][8];
		memset(tar, 0, sizeof(tar));
		for (int i = 0; i < M; i++)
			for (int j = 0; j < K; j++)
				scanf("%d", &tar[i][j]);
		
		P++;
		for (int i = 0; i < M + P + 2; i++) G[i].clear();
		
		int dp[9][6561][9];
			for (int i = 0; i < 9; i++)
				for (int j = 0; j < 6561; j++)
					for (int k = 0; k < 9; k++)
						dp[i][j][k] = 1000000000;
			dp[0][0][0] = 0;
			
			int J = pow3[K];		
			for (int i = 0; i < D; i++){
				for (int j = 0; j < J; j++){
					for (int k = 0; k <= L; k++)
						dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k]);
					for (int k = 0; k < L; k++){
						for (int l = 0; l < K; l++){
							if ((j / pow3[l]) % 3 < 2)
								dp[i + 1][j + pow3[l]][k + 1] = min(dp[i + 1][j + pow3[l]][k + 1], dp[i + 1][j][k] + c[i][l]);
						}
					}
				}
			}
		
		for (int s = 0; s < P; s++){
			int t[8];
			
			if (s != P - 1) for (int i = 0; i < K; i++) scanf("%d", t + i);
			else for (int i = 0; i < K; i++) t[i] = 0;	
			
			for (int i = 0; i < M; i++){
				if (!s) addEdge(P + i + 1, P + M + 1, 1, 0);
				
				int mini = 1000000000;
				int tt[8];
				bool flag = false;
				for (int j = 0; j < K; j++) if (tar[i][j] < t[j]) flag = true;
				if (flag) continue;
				for (int j = 0; j < K; j++) tt[j] = tar[i][j] - t[j];
				int x = encode(tt, K);
				for (int j = 0; j <= L; j++) mini = min(mini, dp[D][x][j]);
				if (mini != 1000000000){
					addEdge(s + 1, P + i + 1, 1, mini);
					//printf("%d -> %d cost %d\n", s + 1, P + i + 1, mini);
				}
			}
			addEdge(0, s + 1, 1 + 1000000000 * (s == P - 1), 0);
		}
		
		printf("%d\n", minCostFlow(0, M + P + 1, N));
	}
	
	return (0);
}