백준 BOJ 11377 - 열혈강호 3

이분 매칭 연습 문제

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

11377번: 열혈강호 3

열혈강호 2와 기본적인 사고의 틀을 공유한다.

하지만 열혈강호 2처럼 문제를 접근한 뒤

매칭 수가 N+K개일때 탈출시키는 방법으로 구현하면

K명보다 더 많은 인원이 일을 2개 하는 경우가 존재해

틀렸습니다를 받게 된다.

 

각 직원마다 정점을 2개로 하는 접근방법은 똑같이 가져가되,

정점 그룹을 두개로 나눠서,

1<=k<=N 에 대한 매칭 갯수를 저장하는 ans1변수와,

N+1<=k<=2N에 대한 매칭 갯수를 저장하는 ans2 변수로 나눠서 관리해줬다.

 

두 정점 그룹이 가지고 있는 이분 그래프의 형태가 똑같기 때문에, 

첫번째 정점 그룹에서 매칭이 실패한 직원이

두번째 정점 그룹에서 매칭을 성공시킬수 있는 방법이 없으므로

두번째 정점 그룹에서 매칭을 성공하는 경우는

반드시 일을 두개 하는 경우이다.

 

따라서 두번째 정점 그룹의 매칭 수인 ans2가 K보다 커질수 없으므로,

ans2 == K 일때 탈출시키면

 

정답을 받아낼 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int N,M,K;
int match[2345] = {0};
bool vis[2345] = {0};

vector<int> g[2345];

bool dfs(int node){
	for(int now : g[node]){
		if(vis[now]) continue;
		vis[now] = true;
		
		if(match[now] == 0 || dfs(match[now])){
			match[now] = node;
			return true;
		}
	}
	return false;
}

int main(){
	int a,b;
	cin >> N >> M >> K;
	for(int i=1; i<=N; i++){
		cin >> a;
		for(int j=0; j<a; j++){
			cin >> b;
			g[i].push_back(b);
			g[i+N].push_back(b);
		}
	}
	
	int ans1 = 0;
	int ans2 = 0;
	
	for(int i=1; i<=N; i++){
		memset(vis, 0, sizeof(vis));
		if(dfs(i)) ans1++;
	}
	
	for(int i=1; i<=N; i++){
		memset(vis, 0, sizeof(vis));
		if(dfs(i+N)) ans2++;
		if(ans2 == K) break;
	}
	
	cout << ans1 + ans2;
	return 0;
}