[BOJ] 11375 : 열혈강호

Drakk·2021년 8월 12일

C boj 네트워크 유량 백준 알고리즘 이분매칭 최대유량

알고리즘 문제풀이

목록 보기

21/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

🧺출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

🔋예제 입출력

🔮예제 입력1
5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1

🔮예제 출력1
4

💉문제 분석

🔋분류

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

🔋난이도

플래티넘IV

💉문제 풀이

🔋해법

그냥 이분매칭 구현문제였습니다.
이때 주의할것이있는데 M은 사용이안되더라구요.
M개의 일중에 최대라고해서 M번 돌려주는건줄 알았더니, 아니네요;;(뭐지..?)

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 1001;
constexpr int INF = 1e9+7;

std::vector<int> adj[MAX];

int d[MAX];
bool visit[MAX];

bool dfs(int current){
	for(int i=0;i<adj[current].size();++i){
		int next = adj[current][i];
		
		if(visit[next]) continue;
		visit[next] = true;
		
		if(d[next] == 0 || dfs(d[next])){
			d[next] = current;
			return true;
		}
	}
	
	return false;
}

int BipartiteMatching(int N){
	int count = 0;
	
	for(int i=1;i<=N;++i){
		memset(visit, false, sizeof(visit));
		if(dfs(i)) ++count;
	}
	
	return count;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int N, M;
	
	std::cin >> N >> M;
	
	for(int i=1;i<=N;++i){
		int T;
		std::cin >> T;
		
		for(int j=0;j<T;++j){
			int a;
			std::cin >> a;
			
			adj[i].push_back(a);
		}
	}
	
	std::cout << BipartiteMatching(N);
}