結果

問題 No.177 制作進行の宮森あおいです！
ユーザー pekempeypekempey
提出日時 2017-02-08 18:09:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,703 ms / 2,000 ms
コード長 5,038 bytes
コンパイル時間 2,419 ms
コンパイル使用メモリ 192,620 KB
実行使用メモリ 45,184 KB
最終ジャッジ日時 2024-12-25 16:51:25
合計ジャッジ時間 9,369 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 12 ms
5,248 KB
testcase_04 AC 12 ms
5,248 KB
testcase_05 AC 100 ms
11,776 KB
testcase_06 AC 314 ms
21,504 KB
testcase_07 AC 9 ms
6,016 KB
testcase_08 AC 42 ms
8,064 KB
testcase_09 AC 1,238 ms
42,496 KB
testcase_10 AC 1,703 ms
45,184 KB
testcase_11 AC 1,580 ms
43,648 KB
testcase_12 AC 1,143 ms
42,752 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-6;

void replace_basis(vector<vector<double>> &a, vector<int> &id, int k, int j) {
	double r = a[k][j];
	for (int i = 0; i < a[0].size(); i++) a[k][i] /= r;
	a[k][j] = 1;
	for (int i = 0; i < a.size(); i++) if (i != k) {
		double r = a[i][j];
		for (int j = 0; j < a[i].size(); j++) a[i][j] -= a[k][j] * r;
		a[i][j] = 0;
	}
	id[k] = j;
}

void simplex(vector<vector<double>> &a, vector<int> &id) {
	const int M = a.size() - 1;
	while (true) {
		int j = max_element(a[M].begin() + 1, a[M].end()) - a[M].begin();
		if (a[M][j] < EPS) break;
		pair<double, int> mn(1e100, INT_MAX);
		for (int i = 0; i < M; i++) {
			if (a[i][j] > EPS) mn = min(mn, make_pair(a[i][0] / a[i][j], i));
		}
		int k = mn.second;
		replace_basis(a, id, k, j);
	}
}

// one-phase simplex
double simplex1(vector<vector<double>> a, vector<double> b, vector<double> c) {
	const int M = a.size();
	const int N = a[0].size();
	vector<vector<double>> table(M + 1, vector<double>(N + M + 1));
	for (int i = 0; i < M; i++) {
		table[i][0] = b[i];
		for (int j = 0; j < N; j++) {
			table[i][j + 1] = a[i][j];
		}
		table[i][N + i + 1] = 1;
	}
	for (int i = 0; i < N; i++) table[M][i + 1] = c[i];
	vector<int> id(M);
	for (int i = 0; i < M; i++) id[i] = N + i + 1;
	simplex(table, id);
	return -table[M][0];
}

// two-phase simplex
// max sum c[i]*x[i]
// s.t. sum(a[i][*]*x[i])<=b[i]
double simplex(vector<vector<double>> a, vector<double> b, vector<double> c) {
	const int M = a.size();
	const int N = a[0].size();
	vector<vector<double>> table(M + 1, vector<double>(N + M + 1));

	for (int i = 0; i < M; i++) {
		table[i][0] = b[i];
		for (int j = 0; j < N; j++) {
			table[i][j + 1] = a[i][j];
			table[M][j + 1] += a[i][j];
		}
		table[M][0] += b[i];
		table[i][N + i + 1] = 1;
	}

	vector<int> id(M);
	for (int i = 0; i < M; i++) id[i] = N + i + 1;

	simplex(table, id);

	for (int i = 0; i < M; i++) {
		if (id[i] >= N + 1) {
			int j;
			for (j = 1; j <= N; j++) {
				if (abs(table[i][j]) > EPS) break;
			}
			if (j == N + 1) return -1e100;
			replace_basis(table, id, i, j);
		}
	}
	for (int i = 0; i <= M; i++) {
		table[i].resize(N + 1);
	}
	table[M][0] = 0;
	for (int i = 0; i < N; i++) {
		table[M][i + 1] = c[i];
	}
	for (int i = 0; i < M; i++) {
		double r = table[M][id[i]];
		for (int j = 0; j <= N; j++) {
			table[M][j] -= table[i][j] * r;
		}
	}
	simplex(table, id);

	return -table[M][0];
}

// one-phase simplex
struct MaxFlowLP2 {
	int n;
	vector<int> cap;
	vector<vector<int>> in, out;
	int es;

	MaxFlowLP2(int n) :
		n(n),
		in(n),
		out(n),
		es(0) {
	}

	void add(int u, int v, int c) {
		cap.push_back(c);
		out[u].push_back(es);
		in[v].push_back(es);
		es++;
	}

	int calc(int s, int t) {
		vector<vector<double>> a;
		vector<double> b;
		vector<double> c(es);

		for (int i = 0; i < es; i++) {
			vector<double> t(es);
			t[i] = 1;
			a.push_back(t);
			b.push_back(cap[i]);
		}

		for (int i = 0; i < n; i++) {
			if (i != s && i != t) {
				vector<double> t(es), tt(es);
				for (int j : out[i]) t[j]++, tt[j]--;
				for (int j : in[i]) t[j]--, tt[j]++;
				a.push_back(t);
				b.push_back(EPS);
				a.push_back(tt);
				b.push_back(EPS);
			}
		}

		for (int j : out[s]) c[j]++;
		for (int j : in[s]) c[j]--;

		return round(simplex1(a, b, c));
	}
};

// two-phase simplex
struct MaxFlowLP {
	int n;
	vector<int> cap;
	vector<vector<int>> in, out;
	int es;

	MaxFlowLP(int n) :
		n(n),
		in(n),
		out(n),
		es(0) {
	}

	void add(int u, int v, int c) {
		cap.push_back(c);
		out[u].push_back(es);
		in[v].push_back(es);
		es++;
	}

	int calc(int s, int t) {
		vector<vector<double>> a;
		vector<double> b;
		vector<double> c(es * 2);

		for (int i = 0; i < es; i++) {
			vector<double> t(es * 2);
			t[i] = t[i + es] = 1;
			a.push_back(t);
			b.push_back(cap[i]);
		}

		for (int i = 0; i < n; i++) {
			if (i != s && i != t && (!in[i].empty() || !out[i].empty())) {
				vector<double> t(es * 2);
				for (int j : out[i]) t[j]++;
				for (int j : in[i]) t[j]--;
				a.push_back(t);
				b.push_back(0);
			}
		}

		for (int j : out[s]) c[j]++;
		for (int j : in[s]) c[j]--;

		return round(simplex(a, b, c));
	}
};

int main() {
	int w;
	cin >> w;
	int n;
	cin >> n;
	vector<int> J(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &J[i]);
	}
	int m;
	cin >> m;
	vector<int> c(m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &c[i]);
	}
	vector<vector<bool>> bad(n, vector<bool>(m));
	for (int i = 0; i < m; i++) {
		int q;
		cin >> q;
		for (int j = 0; j < q; j++) {
			int x;
			cin >> x;
			x--;
			bad[x][i] = true;
		}
	}

	MaxFlowLP2 mf(n + m + 2);
	int src = n + m;
	int dst = src + 1;
	for (int i = 0; i < n; i++) {
		mf.add(src, i, J[i]);
	}
	for (int i = 0; i < m; i++) {
		mf.add(i + n, dst, c[i]);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!bad[i][j]) {
				mf.add(i, j + n, 10101010);
			}
		}
	}
	int f = mf.calc(src, dst);
	if (f >= w) {
		cout << "SHIROBAKO" << endl;
	} else {
		cout << "BANSAKUTSUKITA" << endl;
	}
}
0