Red Salmon

출처 : https://www.acmicpc.net/problem/1587

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1587.cpp

음..나는 이분매칭을 공부하려고 이문제를 열었으나, 이 문제는 이분매칭과는 조금 거리가 있어보인다.

풀이도 전혀 상관없어보인다.

문제가 상당히 어렵게 풀어져있는데 핵심은 매우 간단한 것이다. 하지만 나는 찾지 못하였고 구글링을 통해 문제를 이해하였다.

접근방법

1. 우선 A라는 집합안에서도 매칭이 가능하다. 그리고 답은 최대 매칭을 구하는 것이다. 그렇다면 기본적으로 각 집합을 2로나눈 값을 더한게 최대 매칭이 된다. (하단에 위치한 연결간선은 최대매칭을 해봐도 집합안에서 하는것보다 작게 나온다.)

2. 만약 A또는 B 둘 중 하나가 홀수고 하나는 짝수라면 결국 한녀석은 마지막까지 선택이 되지 않으므로 무시한다.

3. 하지만 둘다 홀수라면 2개씩 짝지어도 하나씩 남는다. 여기서 만약 하단에 입력으로 홀수에서 홀수로가는 간선이 하나라도 존재하면 모두 연결이 되는 것이고, 홀수에서 짝수로만 가거나 짝수에서 짝수로만 가게 된다면 결국 남게 되는 것이다. 그래서 모두 연결되었을때 +1을 해주면 답이 나온다.

예시를 들어보겠다.

A 가 3이고 B가 3이라고 가정하자.

하단의 매칭 부분에서 1->3 혹은 1->1 혹은 3->3 이 존재하면 +1의 경우가 생기는 것이고 나머지 녀석들은 볼필요도없이 나누기 2를 하면 매칭수가 나오게 된다. 

그런데 만약 연결이 1->2 혹은 3->2 혹은 2-> 모든수 라면 동일 집합에서 연결할수 있는 경우가 사라지게 된다. 문제에서 분명 연속된 수끼리만 연결이 된다고 하였으니 불가한 경우가 된다. 다음의 문장을 명심해야한다.

거의 이분 그래프는 이분 그래프와 다르게 nA-1 + nB-1개의 간선을 추가로 가진다. 추가가 되는 간선은 Ai에서 Ai+1로 가는 간선 (1 ≤ i ≤ nA-1)과 Bi에서 Bi+1로 가는 간선 (1 ≤ i ≤ nB-1)이다.

위 문장에 따라 연결이 끈기게 되므로 필요가 없어진다. 그래서 반드시 홀수끼리 연결이 되야 한다. 

실로 간단한 문제이나, 문제가 어렵게 설명된거 같은 느낌이다.