티스토리 뷰
문제 링크 : https://www.acmicpc.net/problem/1298
문제
어느 날 모든 학생들은 한 명이 한 개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 받을 수 있었지만, 애석하게도 N명의 학생들이 정확히 자신의 노트북이 어떤 것인지 알지 못했다. 왜냐하면 그들은 노트북을 구입한 게 바로 어제였기 때문이다.
어차피 새것인 노트북, 바뀐 들 어떠하랴.
그들에게 자신의 노트북이라고 생각되는 노트북들을 얘기해 보라고 했다.
이번에는 정말 신기하게도 그들 각각이 노트북을 여러 개 선택한 것이었다! “이것 아니면 이것 아니면 이것 아니면 이것 일거 같아요”라카더라.
우리의 목적은 이들의 요구를 가장 많이 만족시키는 것이다.
요컨대, 자신이 자신의 것 같다고 얘기한 노트북을 갖는 사람을 최대화하라는 소리다.
입력
첫째 줄에는 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 N(1 ≤ N ≤ 100)과 노트북 예상의 개수 M(0 ≤ M ≤ 5,000) 주어진다.
둘쨋줄에서 M+1번째 줄 까지는 각각 한 줄마다 a b가 주어지는데, 이는 a번 사람이 b번 노트북을 자신의 것이라고 생각한다는 의미를 갖는다.
노트북과 사람의 번호는 1보다 크거나 같고, N보다 작거나 같다. 두 사람 또는 두 노트북이 같은 번호를 갖는 경우는 없다.
출력
최대로 만족될 수 있는 사람 수를 출력한다.
풀이
사람 vs 노트북 가능한 많이 사람들이 노트북을 가져갈 수 있게 해주자. DFS 를이용하여 구해주자 축사 배정 상어 식사 다 같은 문제라고 생각한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int d[101];
int visited[101];
vector<int> a[101];
int dfs(int x) {
int i;
for( i = 0 ; i < a[x].size() ; i++) {
int y = a[x][i];
if(visited[y]) continue;
visited[y] = 1;
if(d[y] == 0 || dfs(d[y])) {
d[y] = x;
return 1;
}
}
return 0;
}
int main()
{
int i,j;
int N , M;
cin >> N >> M;
int x,y;
for( i=1; i<= M ; i++) {
cin >> x >> y;
a[x].push_back(y);
}
int ans = 0;
for(i=1; i<= N ; i++) {
memset(visited,0,sizeof(visited));
if(dfs(i)) ans++;
}
cout << ans;
return 0;
}
|
'백준 (BOJ) > 이분매칭' 카테고리의 다른 글
백준)1864 - 돌멩이 제거 (0) | 2019.05.02 |
---|---|
백준)2188-축사 배정 (0) | 2019.05.02 |
백준) 1671-상어의 저녁식사 (0) | 2019.05.02 |
- Total
- Today
- Yesterday
- dfs
- 백트래킹
- 이분 매칭
- #스페인어 #스페인어인강 #스페인어공부 #시원스쿨스페인어
- BFS
- 정렬
- CSS
- HTML
- 다익스트라
- 그래프
- 이분매칭
- KVK4
- greedy
- 라이즈오브킹덤즈
- 플로이드
- A
- 그리디알고리즘
- 백트레킹
- 그리디
- php
- JavaSwing
- 사이크
- 사이클
- stri
- 라오킹전사
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |