[백준BOJ] 11376 열혈강호2

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

11376번: 열혈강호 2

---

문제해설

열혈강호 1 에서 바뀐 조건은 한사람이 2가지의 일을 할 수 있다는 것이다.

visit을 초기화 하고나서,

2번의 flow를 발생시키면 된다.

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------
 
#define MAX_N 1001
vector<int> map[MAX_N];
 
int employee[MAX_N];
int work[MAX_N];
bool visit[MAX_N];
 
bool fun(int s) {
	visit[s] = true;
	for (int i = 0; i < map[s].size(); i++) {
		if (work[map[s][i]] == -1 || (!visit[work[map[s][i]]] && fun(work[map[s][i]]))) {
			employee[s] = map[s][i];
			work[map[s][i]] = s;
			return true;
		}
	}
	return false;
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M; cin >> N >> M;
 
	for (int i = 1; i <= N; i++) {
		int s; cin >> s;
		for (int j = 0; j < s; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(employee, -1, sizeof(employee));
	memset(work, -1, sizeof(work));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (employee[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans++;
			if (fun(i)) ans++;
		}
	}
	cout << ans << endl;
}

 

---

기타