백준
백준 2188 - 축사 배정(C++)
공대생의 잡다한 사전
2023. 2. 11. 17:35
문제 링크입니다. https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해
www.acmicpc.net
이분 매칭을 이용하는 문제입니다.
이분 매칭이라는 알고리즘 설명이 잘나와있는 블로그입니다. 참고해주세요.
https://yjg-lab.tistory.com/209
[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)
이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 말합니다.
yjg-lab.tistory.com
자세한 것은 코드를 참고해주세요
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<int, int>
#define F first
#define S second
using namespace std;
int N, M;
vector<int> Match[1011];
vector<int> a_match, b_match;
bool check[1011];
bool dfs(int start){
if(check[start]) return false;
check[start] = true;
for(int i = 0; i < Match[start].size(); i++){
int x = Match[start][i];
if(b_match[x] == -1 || dfs(b_match[x])){
a_match[start] = x;
b_match[x] = start;
return true;
}
}
return false;
}
void solve(){
a_match = vector<int>(N+1, -1);
b_match = vector<int>(M+1, -1);
int size = 0;
for(int i = 1; i <= N; i++){
memset(check, false, sizeof(check));
if(dfs(i)) size++;
}
cout << size;
}
int main() {
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i = 1; i <= N; i++){
int n;
cin >> n;
for(int j = 1; j <= n; j++){
int x;
cin >> x;
Match[i].push_back(x);
}
}
solve();
return 0;
}
질문 및 조언은 댓글을 남겨주세요