SRM 231 DIV1 Hard Mixture

問題 Editorial

問題

化合物がM種類ある。
化合物はavailableMixturesによって表され、N種類の薬品の重み付き和として表される。また、それぞれ値段もついている。
その中からそれぞれいくらかずつ混ぜて別の化合物mixtureを作りたい。
それぞれの混ぜる量は整数で無くても良い。
作る化合物はそれぞれの薬品がちょうどの量なければいけない。
値段を最小化せよ。目的の化合物が作れない場合は-1を返せ

• 1 <= N <= 10
• 1 <= M <= 10

解答

線形計画問題そのまま。
線形計画法のライブラリがあるかどうかの問題になる。
Practice Roomのwataさんのコードを参考にした

コード

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <limits>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef vector<int> vi; 

typedef long double Num; typedef vector<Num> Vec; typedef vector<Vec> Mat;
const Num Inf = numeric_limits<Num>::infinity();
const Num NoSolution = numeric_limits<Num>::quiet_NaN();
#define IsSolution(x) (x == x)
const Num EPS = 1e-10;

//	Maximize: c * x
//	A * x <= b
//	x     >= 0
Num simplex(const Mat& A, const Vec& b, const Vec& c) {
	const int m = A.size(), n = A[0].size();
	Mat D(m+1, Vec(n+1)); vi id(n+m+1);
	rer(i, 0, n+m) id[i] = i;
	rep(i, m) {
		rep(j, n) D[i][j] = -A[i][j];
		D[i][n] = b[i];
	}
	rep(j, n) D[m][j] = c[j];
	while(1) {
		int r = m, s = n+m;
		rep(i, m) if(D[i][n] < -EPS && id[n+r] > id[n+i]) r = i;
		rep(j, n) if(D[m][j] > EPS && id[s] > id[j]) s = j;
		if(r == m && s == n + m) break;
		if(id[n + r] < id[s]) {
			s = n + m;
			rep(j, n) if(D[r][j] > EPS && id[s] > id[j]) s = j;
		}else {
			r = m;
			rep(i, m) if(D[i][s] < -EPS && id[n+r] > id[n+i]) r = i;
		}
		if(r == m) { /* Unbounded */ return NoSolution; }
		if(s == n + m) { /* NoSolution */ return NoSolution; }
		swap(id[s], id[n+r]);
		D[r][s] = 1. / D[r][s];
		rer(j, 0, n) if(j != s) D[r][j] *= -D[r][s];
		rer(i, 0, m) if(i != r && abs(D[i][s]) > EPS) {
			rer(j, 0, n) if(j != s) D[i][j] += D[r][j] * D[i][s];
			D[i][s] *= D[r][s];
		}
	}
	return D[m][n];
}

struct Mixture {
	double mix(vector <int> mixture, vector <string> availableMixtures) {
		int m = mixture.size(), n = availableMixtures.size();
		Mat A(m * 2, Vec(n)); Vec b(m * 2), c(n);
		rep(j, m) b[j] = mixture[j], b[m+j] = -mixture[j];
		rep(i, n) {
			stringstream ss(availableMixtures[i]);
			rep(j, m) {
				int x; ss >> x;
				A[j][i] = x; A[m+j][i] = -x;
			}
			int price; ss >> price;
			c[i] = -price;
		}
		Num s = simplex(A, b, c);
		if(!IsSolution(s)) return -1;
		return -s;
	}
};