ACMICPC 1671 상어의 저녁식사

문제

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다.

만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다.

그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다.

상어들은 김재홍의 말을 모두 듣는다. N마리 상어의 크기, 속도, 지능이 주어졌을 때, 살아남을 수 있는 상어의 최소값을 구하시오.

첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다.

둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다.

첫째 줄에 살아남을 수 있는 상어의 최소값을 출력한다.

정점은 모든 상어들. 엣지는 a -> b 라 할 때 a 가 b를 먹을 수 있는 경우에만 연결해주면 된다. - canEat() 함수 -

이때 주의할 것이 있는데, 두 상어의 스펙이 같을 경우 예외처리를 해주지 않으면 서로 서로

먹어버리게 된다. (ex input:

1 1 1

출력이 1이어야 하지만 예외처리를 안해주면 0이 나온다)

물론 자기 자신또한 먹을 수 없다는 것도 생각해주어야 하는 것을 잊지 말고.

그 점만 주의하면서 엣지를 연결해주고 이분 매칭 dfs를 각 정점마다 2번씩 돌려주면 된다.