💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

🧺출력
첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

🔋예제 입출력

🔮예제 입력

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

🔮예제 출력

4

💉문제 분석

🔋분류

네트워크유량, 최대유량, 이분매칭

🔋난이도

플래티넘IV

💉문제 풀이

🔋해법

일반적인 이분매칭문제입니다.
딱히 주의할것은없습니다.

🔋소스코드

#include <bits/stdc++.h>

//Static variables
constexpr int MAX = 201;
constexpr int INF = 987654321;

//AlgoCapsule
class AlgoCapsule {
public:
	void Run() {
		Input();
		Solve();
		Output();
	}

	void Input() {
		std::cin >> N >> M;

		for (int i = 1; i <= N; ++i) {
			int T;
			std::cin >> T;
			for (int k = 0; k < T; ++k) {
				int a;
				std::cin >> a;
				adj[i].push_back(a);
			}
		}
	}

	void Solve() {
		for (int i = 1; i <= N; i++) {
			std::fill(visit, visit + MAX, false);
			if (BipartiteMatching(i)) count++;
		}
	}

	void Output() {
		std::cout << count;
	}

	bool BipartiteMatching(int start) {
		for (int i = 0; i < adj[start].size(); ++i) {
			int x = adj[start][i];

			if (visit[x]) continue;
			visit[x] = true;

			if (d[x] == 0 || BipartiteMatching(d[x])) {
				d[x] = start;
				return true;
			}
		}
		return false;
	}

	AlgoCapsule() { }
private:
	bool visit[MAX];
	int d[MAX];
	std::vector<int> adj[MAX];
	int N, M, count = 0;
};

//Module Entry
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	AlgoCapsule AC;
	AC.Run();

	return 0;
}

이번에는 처음으로 저가 만든 알고리즘 문제풀이용 기본소스코드를 사용했습니다.
알고리즘 문제풀이용 기본 소스코드 보러가기

이분매칭문제는 많이 안풀어봐서, 이분매칭문제 처음 푸시는분들에게는 초반 손풀기용으로 괜찮은 문제같습니다.

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~