백준 11376번 - 열혈강호 2

 

 

* 문제 링크

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

11376번: 열혈강호 2

 

 

 

문제 내용 요약

 

강호네 회사에서는 또 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000)

 

직원 한 명은 2 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다.

 

최대 몇 개의 일을 할 수 있을까?

 

 

 

 

접근법

 

 

11375번 열혈강호 문제를 먼저 풀어오기를 추천한다.

 

 

https://syerco0.tistory.com/19

백준 11375번 - 열혈강호

 

 

위의 문제랑 비슷하게 접근하면 된다.

 

"이분 매칭"을 쓰는 것만 알면 쉽다.

 

 

한 직원을 2개의 노드로 분리해보자.

 

할 수 있는 일은 당연히 같게 해줘야한다.

 

 

어차피 할 수 있는 최대의 일의 수를 구하는 것이 문제이기 때문에,

 

그리고 이분 매칭의 기본은 각 집합의 원소 1개씩만 매칭을 시키는 것이기 때문에

 

직원이 2배 있다고 생각하고, 11375번 열혈강호 문제를 그대로 풀어주면

 

금방 AC 를 받을 수 있을 것이다.

 

 

특별히 그림 설명이 추가적으로 필요할 것 같지는 않아서 생략한다.

 

날먹

 

진짜로 더 설명할게 없다.

 

 

 

내 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> emp[2002];
int work_to_emp[1001];
bool vstd[2001];

bool find_work(int n) {
	if(vstd[n]) return false;
	vstd[n]=1;
	for(int i:emp[n]) {
		if(work_to_emp[i]==0||find_work(work_to_emp[i])) {
			work_to_emp[i]=n;
			return true;
		}
	}
	return false;
}

int main() {
	int n,m,s=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		int t;
		scanf("%d",&t);
		for(int j=1;j<=t;j++) {
			int u;
			scanf("%d",&u);
			emp[2*i-1].push_back(u);
			emp[2*i].push_back(u);
		}
	}
	for(int i=1;i<=2*n;i++) {
		memset(vstd,0,sizeof(vstd));
		if(find_work(i)) {
			s++;
		}
	}
	cout<<s;
}

 

 

 

여담

 

사실 전 글로 "11375번 열혈강호"를 썼다보니,

 

이 글을 쓰는 것은 일종의 날로 먹는 행위이긴 하다.

 

하지만 혹시나 진짜 정말로 혹시나 찾는 사람이 있을 수도 있어서 썼다.

 

 

근데 사실 나는 날로 먹는걸 좋아하긴 한다.

 

싫어하는 사람이 있을까?

 

 

몰?루