[BOJ] 6786번 Blood Distribution
[BOJ] 6786번 Blood Distribution 풀이
2025년 12월 16일 · 1 min read
[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";
}