[백준] 1671 상어의 저녁식사 (C++)

신촌연합 중급반 연습문제로 풀다가 푼 문제.

1671번: 상어의 저녁식사

 

문제 요약)

N마리의 상어가 있다.

N마리의 상어는 크기, 속도, 지능이 있다. 이 세 개 모두 다른 상어보다 크거나 같으면 다른 상어를 먹을 수 있다.

각 상어는 최대 2마리까지 먹을 수 있다.

남아있는 상어가 최소가 되게 먹었을 때, 남아있는 상어의 수는?

 

 

1.

상어가 다른 상어를 먹는다...

각 상어가 최대 2마리까지 먹을 수 있음...

최대한 많이 먹어야 함...

 

 

2.

이거 어디서 본 상황이다. 플로우가 떠오른다.

https://www.acmicpc.net/problem/11376 (열혈강호 2)

 

 

3.

각 상어마다 노드를 2개씩 주자.

하나는 먹는 쪽, 하나는 먹히는 쪽.

소스 -> 먹는 쪽에 2의 용량을 주자. 2개까지 먹을 수 있으므로

먹을 수 있는 것들을 간선으로 이어주자.

모든 먹히는 쪽 -> 싱크에 1의 용량을 주자. 1이 흘러들어오면 먹힌 것이다.

이분매칭을 이용해서도 풀 수 있을 것처럼 생겼다. (가능)

 

 

4.

답은 (N-최대유량)이다. 최대유량 값은 먹힌 상어의 수이므로!

 

 

코드

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 998244353
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct str {
	ll a, b, c;
};

ll n;
ll cap[110][110];   //용량
ll flow[110][110];
ll cache[110];      //이전 노드 저장하는 용도
vector<ll> adj[110];
vector<str> jaws(51);

void add_edge(ll from, ll to, ll c) {
	adj[from].push_back(to);
	adj[to].push_back(from);
	cap[from][to] = c;
}

ll Edmond_Karp(ll source, ll sink) {
	ll max_flow = 0;
	while (1) {
		queue<ll> q;
		q.push(source);
		memset(cache, -1, sizeof(cache));
		cache[source] = 0;
		while (q.size()) {
			ll cur = q.front();
			q.pop();
			for (auto nxt : adj[cur]) {
				if (cache[nxt] == -1 && cap[cur][nxt] - flow[cur][nxt] > 0) {
					cache[nxt] = cur;
					q.push(nxt);
					if (nxt == sink) break;
				}
			}
		}
		if (cache[sink] == -1) break;
		ll min_cap = 9876543210;
		for (ll i = sink; i != source; i = cache[i]) {
			ll bef = cache[i];
			min_cap = min(min_cap, cap[bef][i] - flow[bef][i]);
		}
		max_flow += min_cap;
		for (ll i = sink; i != source; i = cache[i]) {
			ll bef = cache[i];
			flow[bef][i] += min_cap;
			flow[i][bef] -= min_cap;
		}
	}
	return max_flow;
}

bool can_eat(ll i, ll j) {
	str x = jaws[i];
	str y = jaws[j];
	if (x.a == y.a && x.b == y.b && x.c == y.c) {
		if (i < j) return true;
		else return false;
	}
	if (x.a >= y.a && x.b >= y.b && x.c >= y.c) return true;
	else return false;
}

void solve() {
	cin >> n;
	for (ll i = 1; i <= n; i++) cin >> jaws[i].a >> jaws[i].b >> jaws[i].c;
	for (ll i = 1; i <= n; i++) {
		add_edge(0, i, 2);
		add_edge(n + i, 2 * n + 1, 1);
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			if (i == j) continue;
			if (can_eat(i, j)) add_edge(i, n + j, 1);
		}
	}
	cout << n - Edmond_Karp(0, 2 * n + 1) << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
	return 0;
}

 

플로우. 멈춰!