https://www.acmicpc.net/problem/11375
11375번: 열혈강호
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제해설
밑의 문제와 동일한 문제입니다( 입력 범위만 살짝 다릅니다 )
2019/10/13 - [알고리즘/BOJ] - [백준BOJ] 2188 축사 배정
[백준BOJ] 2188 축사 배정
https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 N개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게..
polohee81.tistory.com
전체코드
#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 cow[MAX_N]; int area[MAX_N]; bool visit[MAX_N]; bool fun(int s) { visit[s] = true; for (int i = 0; i < map[s].size(); i++) { if (area[map[s][i]] == -1 || (!visit[area[map[s][i]]] && fun(area[map[s][i]]))) { cow[s] = map[s][i]; area[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(cow, -1, sizeof(cow)); memset(area, -1, sizeof(area)); int ans = 0; for (int i = 1; i <= N; i++) { if (cow[i] == -1) { memset(visit, false, sizeof(visit)); if (fun(i)) ans++; } } cout << ans << endl; }
기타
'알고리즘 > [C++]BOJ' 카테고리의 다른 글
| [백준BOJ] 11376 열혈강호2 (0) | 2019.10.13 |
|---|---|
| [백준BOJ] 2188 축사 배정 (0) | 2019.10.13 |
| [BOJ백준] 10000 원 영역 (0) | 2019.10.13 |