Codeforces ECR #108 : F. Chests and Keys

うーん、自力で解ける気がしない。
https://codeforces.com/contest/1519/problem/F

問題

N個の箱とM個の錠がある。
i番の箱にはコインがA[i]個入っている。
j番の錠を開ける鍵は、コインB[j]個で入手することができる。

先手は、各箱に1～M番の錠をつけることができる。ただし、i番の箱にj番の錠をつけるにはコストC[i][j]かかる。
後手はいくつか鍵を買い、それですべての錠を解除できる箱を開ける。

先手は最適な錠の付け方をし、後手がどんな鍵の買い方をしても、鍵を買うのにかかるコインが箱を開けて手に入れられるコイン以上になるようにしたい。
かかるコストの総和を最小化せよ。

解法

source→箱に相当する点→錠に相当する点→sink という構成をもつフローを考える。
sourceから箱に相当する点への辺は容量A[i]であり、錠に相当する点からsinkへの辺は容量B[i]である。

ここに箱に相当する点から錠に相当する点へ容量無限大の辺を張ることを考える。
ProjectSelectionProblemの要領で考えると、このグラフがsum(A)のフローを流せれば、鍵を買うのにかかるコインが箱から手に入れるコイン以上となり、先手が条件を満たすことになる。
箱に相当する点iから錠に相当する点jへ容量無限大の辺を張るには、コストがC[i][j]かかると考え、このグラフにsum(A)のフローを流すのにかかる最小コストを考えよう。

愚直に最大フローを色んな辺の構成で試すのはTLEする。
今回、あいにく流れるフローの量は小さいので、1辺ずつ追加したときフローの流れ方がどうなるかを総当たりしながら、辺を足すかどうかDPしよう。

int N,M;
int A[6],B[6];
int C[6][6];
ll dp[5<<20];

vector<int> decode(int cur) {
	int i;
	vector<int> R;
	FOR(i,N+1) {
		R.push_back(cur%5);
		cur/=5;
	}
	R.push_back(cur%7);
	cur/=7;
	R.push_back(cur%7);
	reverse(ALL(R));
	return R;
}

int encode(vector<int>& V) {
	int cur=0;
	int i;
	cur=V[0];
	cur=cur*7+V[1];
	FOR(i,N+1) {
		cur=cur*5+V[2+i];
	}
	assert(cur<5<<20);
	return cur;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int sum=0;
	FOR(i,N) {
		cin>>A[i];
		sum+=A[i];
	}
	FOR(i,M) cin>>B[i];
	FOR(y,N) FOR(x,M) cin>>C[y][x];
	
	ll ret=1LL<<60;
	FOR(i,5<<20) dp[i]=1LL<<60;
	dp[0]=0;
	FOR(i,5<<20) if(dp[i]<1LL<<60) {
		vector<int> S=decode(i);
		int s=0;
		FOR(j,N) s+=S[2+j];
		x=S[1];
		y=S[0];
		if(y>=M) continue;
		/*
		cout<<i<<" ";
		FORR(v,S) cout<<v;
		cout<<" "<<dp[i]<<" "<<s<<endl;
		*/
		FOR(j,5) {
			if(S[2+x]+j>A[x]) continue;
			if(S.back()+j>B[y]) continue;
			int c=(j==0)?0:C[x][y];
			
			if(s+j>=sum) {
				//cout<<"  !"<<j<<" "<<c<<" "<<dp[i]+c<<endl;
				ret=min(ret,dp[i]+c);
			}
			else {
				vector<int> T=S;
				// go next
				T[2+x]+=j;
				if(x==N-1) {
					T.back()=0;
					T[1]=0;
					T[0]++;
					if(T[0]==M) continue;
				}
				else {
					T.back()+=j;
					T[1]++;
				}
				k=encode(T);
				dp[k]=min(dp[k],dp[i]+c);
				
			}
			
		}
		
	}
	if(ret==1LL<<60) ret=-1;
	cout<<ret<<endl;
	
}

まとめ

こういう変則的なフローの流し方、自分で1から考えるのしんどいな。