🧺입력
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.
🧺출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
🔮예제 입력1
5 5 2 1 2 1 1 2 2 3 3 3 4 5 1 1
🔮예제 출력1
4
DFS, 이분매칭, 최대유량, 네트워크 유량
플래티넘IV
그냥 이분매칭 구현문제였습니다.
이때 주의할것이있는데 M은 사용이안되더라구요.
M개의 일중에 최대라고해서 M번 돌려주는건줄 알았더니, 아니네요;;(뭐지..?)
#include <bits/stdc++.h>
constexpr int MAX = 1001;
constexpr int INF = 1e9+7;
std::vector<int> adj[MAX];
int d[MAX];
bool visit[MAX];
bool dfs(int current){
for(int i=0;i<adj[current].size();++i){
int next = adj[current][i];
if(visit[next]) continue;
visit[next] = true;
if(d[next] == 0 || dfs(d[next])){
d[next] = current;
return true;
}
}
return false;
}
int BipartiteMatching(int N){
int count = 0;
for(int i=1;i<=N;++i){
memset(visit, false, sizeof(visit));
if(dfs(i)) ++count;
}
return count;
}
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int N, M;
std::cin >> N >> M;
for(int i=1;i<=N;++i){
int T;
std::cin >> T;
for(int j=0;j<T;++j){
int a;
std::cin >> a;
adj[i].push_back(a);
}
}
std::cout << BipartiteMatching(N);
}
N이랑 M헷갈려서 한번 틀렸네용.
4일만에 푸는 알고리즘문제네용ㅋㅋ
요즘에 웹앱개발에 빠져가지고, 알고리즘문제를 통안풀었습니다.
손풀기겸 이분매칭문제 하나풀었습니다.
앱은 코틀린배우고있고, 웹쪽은 html, css, js(jquery)등등 배우는중입니다.
나중에 웹개발감각좀 생기면 php도 도전해봐야겠군요..!
게임, 웹, 그림 모두 마스터하는 그날까지!
(그림은 워낙 똥손이라서, 이번생애 애니일러 그려보는게 꿈인데 가능할까요..ㅠㅠ)궁금한 부분있으시면 댓글로 질문주세요~~