[백준BOJ] 11377 열혈강호 3

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

11377번: 열혈강호 3

---

문제해설

열혈강호3  = 열혈강호1 + 열혈강호2

라고 보시면 되는 문제입니다. 

• 우선 모든 사람에게 한가지 일을 시킵니다.
• 한가지 일을 한 사람들 중에서 한가지일을 더 시킵니다. 

---

전체코드

#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 cout1(a) {cout << a << endl;}
#define cout2(a,b) {cout << a << " " < b << endl;}
//--------------------------------------------------------------------------------------
 
#define MAX_N 1001
vector<int> map[MAX_N];
int work[MAX_N];
int worked[MAX_N];
bool visit[MAX_N];
int workCnt[MAX_N];
bool dfs(int x) {
	visit[x] = true;
	for (int i = 0; i < map[x].size(); i++) {
		int y = map[x][i];
		if (worked[y] == -1 || (visit[worked[y]] == false && dfs(worked[y]))) {
			work[x] = y;
			worked[y] = x;
			return true;
		}
	}
	return false;
}
 
 
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M, K; cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		int C; cin >> C;
		for (int j = 0; j < C; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(work, -1, sizeof(work));
	memset(worked, -1, sizeof(worked));
	int ans = 0;
	int k = 0;
	for (int i = 1; i <= N; i++) {
		if (work[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (dfs(i)) {
				workCnt[i]++;
				ans++;
			}
		}
	}
 
	for (int i = 1; i <= N; i++) {
		if (workCnt[i] == 1) {
			memset(visit, false, sizeof(visit));
			if (k < K && dfs(i)) {
				ans++;
				k++;
			}
		}
	}
 
	cout << ans << endl;
}

---

기타