백준 11378 열혈강호 4 (c++) : 피너클

11378번: 열혈강호 4

https://www.acmicpc.net/problem/11378

 

이분 매칭이랑 그리드를 이용해서 풀었다.

 

이분 매칭은 사람과 일을 매칭해준다.

사람이 일을 할 수 있으면 true를 반환하고 없으면 false를 반환한다.

bool dfs(int now) {
	if (visited[now]) return false;
	visited[now] = true;

	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];

		if (match[next] == -1 || dfs(match[next])) {
			match[next] = now;
			return true;
		}
	}
	return false;
}

 

이 문제에서 모든 사람은 한번씩은 일 할 수 있다.

그 후 k번 추가로 누군가들이 일할수있다.

이 누군가들을 어떻게 구해야 할까

 

그냥 일 많이 할 수 있는 놈들한테 최대한 몰아주면 된다.

int n, m, k;
vector<int> v[1001];
vector<pair<int, int>> c;

int match[1001];
bool visited[1001];

사용할 변수들이다.

c는 일 많이 할 수 있는놈 구할때 사용할것이다. pair<할 수 있는 일의 양, 번호> 이 순서다.

 

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a;
		c.push_back({ a, i });
		while (a-- > 0) {
			cin >> b;
			v[i].push_back(b);
		}
		sort(v[i].begin(), v[i].end());
	}

	sort(c.begin(), c.end());

이렇게 입력받고 c를 정렬한다.

	int ans = 0;
	for (int i = 0; i < 1001; i++) match[i] = -1;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 1001; j++) visited[j] = false;

		if (dfs(i)) ans++;
	}

그 후 이분매칭 한번 돌려준 다음에

	for (int i = n-1; i >= 0; i--) {

		while (k > 0) {
			for (int j = 0; j < 1001; j++) visited[j] = false;
			if (dfs(c[i].second)) {
				ans++;
				k--;
			}
			else break;
		}
	}

	cout << ans << '\n';

일 많이 할 수 있는 순서대로 k번만큼 최대한 돌려주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, k;
vector<int> v[1001];
vector<pair<int, int>> c;

int match[1001];
bool visited[1001];

bool dfs(int now) {
	if (visited[now]) return false;
	visited[now] = true;

	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];

		if (match[next] == -1 || dfs(match[next])) {
			match[next] = now;
			return true;
		}
	}
	return false;
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a;
		c.push_back({ a, i });
		while (a-- > 0) {
			cin >> b;
			v[i].push_back(b);
		}
		sort(v[i].begin(), v[i].end());
	}

	sort(c.begin(), c.end());

	int ans = 0;
	for (int i = 0; i < 1001; i++) match[i] = -1;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 1001; j++) visited[j] = false;

		if (dfs(i)) ans++;
	}

	for (int i = n-1; i >= 0; i--) {

		while (k > 0) {
			for (int j = 0; j < 1001; j++) visited[j] = false;
			if (dfs(c[i].second)) {
				ans++;
				k--;
			}
			else break;
		}
	}

	cout << ans << '\n';


	return 0;

}

전체코드다.