노트북의 주인을 찾아서
문제 해석
- N명의 학생들이 최대한 많은 노트북을 선택하도록 하는 문제입니다.
설계(X)
- 이분매칭 알고리즘을 사용하는 문제입니다.
- crocus님과 ACM-ICPC 상탈사람님의 블로그를 통해 이분매칭 알고리즘의 개념과 구현방법을 익혔습니다..
- 정점을 두개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝점이 서로 다른 그룹에 속하는 형태의 그래프를 이분그래프라고 합니다.
- 이분그래프인 A와 B그래프가 있을 때, A그래프의 하나의 정점이 B그래프의 하나의 정점만 가지도록 구성된 것을 이분매칭이라고 합니다.
- dfs를 이용하여 이분매칭을 구현할 수 있습니다(O(VxE))
- 모든 정점에 대해서 매칭을 dfs로 시도합니다.
- 해당 정점의 모든 간선에 대해서 매칭이 되어있지 않은 정점이 있거나 이미 매칭된 정점이 다른정점과 매칭이 가능한 지에 대해 조사를 하고, 매칭을 시킵니다.
구현(X)
코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 101
vector<int> adj[MAXN];
bool visited[MAXN];
int N,M;
int b_match[MAXN];
int dfs(int here){
if (visited[here]) return 0;
visited[here] = true;
for (int i = 0 ; i < adj[here].size(); i++){
int next = adj[here][i];
if (!b_match[next] || dfs(b_match[next])){
b_match[next] = here;
return 1;
}
}
return 0;
}
int bmatch(){
int ret = 0;
for (int i = 1; i <=N; i++){
memset(visited,false,sizeof(visited));
if (dfs(i)) ret++;
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0 ; i <M;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
}
cout << bmatch() <<"\n";
return 0;
}
디버깅
제출결과
- 0ms
마무리
- 이분매칭을 이용하는 문제였습니다. 이분매칭 자체 알고리즘은 이해를 하였지만, 이를 어디에 써야하는지 아직은 이해를 하기 어렵습니다.
- 조금 더 문제에 적용을 해봐야 알 것 같습니다.