結果

問題 No.177 制作進行の宮森あおいです！
ユーザー threepipes_sthreepipes_s
提出日時 2015-05-19 03:20:28
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,557 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 66,556 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 05:40:11
合計ジャッジ時間 2,344 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 RE -
testcase_07 WA -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;
int w, n, m;
int J[50];
int C[50];
struct Node{
	int id;
	vector<int> edge;
};
int cap[50][50];
Node node[102];
bitset<50> bs;
bitset<102> used;
int dfs(int, int);
void add(int, int, int);

int main(){
	cin >> w >> n;
	for (int i = 0; i<n; i++) cin >> J[i];
	cin >> m;
	for (int i = 0; i<m; i++) cin >> C[i];
	int nodes = 2 + n + m;
	for (int i = 0; i<nodes; i++) node[i].id = i;
	for (int i = 0; i<n; i++){
		// nodeの0から1+iにJ[i]の辺を張る
		add(0, 1 + i, J[i]);
	}
	for (int i = 0; i<m; i++){
		int q;
		cin >> q;
		bs.reset();
		for (int j = 0; j<q; j++){
			int x;
			cin >> x;
			bs.set(x-1);
		}
		for (int j = 0; j<n; j++){
			if(!bs.test(j)){
				// nodeの1+jから1+n+iにJ[j]の辺を張る
				add(1 + j, 1 + n + i, J[j]);
			}
		}
		// nodeの1+n+iから1+n+mにC[i]の辺を張る
		add(1 + n + i, 1 + n + m, C[i]);
	}
	int res = 0;
	while (true){
		used.reset();
		int flow = dfs(0, 1000000);
		if (flow == 0) break;
		res += flow;
	}
	cout << res << endl;
}

int dfs(int from, int flow){
	if (from == n + m + 1) return flow;
	if (used.test(from)) return 0;
	used.set(from);
	for (auto i = node[from].edge.begin(); i != node[from].edge.end(); i++){
		int to = *i;
		if (!cap[from][to]) continue;
		int f = dfs(to, min(flow, cap[from][to]));
		if (f == 0) continue;
		cap[from][to] -= f;
		cap[to][from] += f;
		return f;
	}
	return 0;
}

void add(int from, int to, int flow){
	node[from].edge.push_back(to);
	cap[from][to] = flow;
}
0