[BOJ] 6786번 Blood Distribution

12/16/2025 · 1 min read

BOJPS

[P2] Blood Distribution

tag : max_flow
link : https://www.acmicpc.net/problem/6786

source -> 1 ~ 8 혈액, 9 ~ 16 환자 -> sink 순으로 모델링하면 된다.

bool chk[8][8] = {
	{1, 0, 0, 0, 0, 0, 0, 0},
	{1, 1, 0, 0, 0, 0, 0, 0},
	{1, 0, 1, 0, 0, 0, 0, 0},
	{1, 1, 1, 1, 0, 0, 0, 0},
	{1, 0, 0, 0, 1, 0, 0, 0},
	{1, 1, 0, 0, 1, 1, 0, 0},
	{1, 0, 1, 0, 1, 0, 1, 0},
	{1, 1, 1, 1, 1, 1, 1, 1}
};
 
void solve(){
	Dinic<int> flow(22);
	int st = 20, en = 21;
	for(int i = 0; i < 8; i++){
		int x; cin >> x;
		flow.add_edge(st, i, x);
	}
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			if(!chk[j][i]) continue;
			flow.add_edge(i, j + 1 + 8, INF); 
		}
	}
	for(int i = 9; i <= 16; i++){
		int x; cin >> x;
		flow.add_edge(i, en, x);
	}
	cout << flow.maximum_flow(st, en) << "\n";
}