사실 이 문제 이분 그래프가 안되기때문에 다른 방식으로 유도한 문제이긴 합니다.

테케가 약한걸까요 ??

사실 저도 "BOJ 1017 소수쌍" 문제에서 홀수, 짝수 이분 그래프로 나누지 않고 처음에 그냥 소수로 이어지는 것들 다 이어서 제출했더니 AC 나온적이 있습니다.

저도 명확히 왜 되는지 말씀을 못드리겠네요..

출제 의도는 이분 매칭 사용하지 말라! 엿는데.. 뭉그러졋네욬ㅋㅋㅋ큐ㅠㅠ

A그룹에 속하는 a1, a2, a3,... an / B그룹에 속하는 b1, b2, b3.... bn
을 이분 매칭 시키면 되는거 아닌가요?
ai와 bj가 매칭되면 bi와 aj가 매칭되는 특수한 형태라 가능한거 같은데요.
ai와 bj가 매칭 될때 aj와 bi가 매칭시키면 최대 유량일테고,
만약 ai-bj인데 aj-bk , al-bi 형태로 매칭되있으면,
결국 1. k와 l이 연결되있거나, 2. 위의 형태가 계속되거나
해서 i와 j를 연결시키는 사이클이 생길 수 밖에 없고
이를 소거해가면서 연결하다보면 변형이 가능할거 같아요.
참 설명이 쓰레기같은데 아랫분이 정답을 알려주실겁니다..

일반적인 그래프 매칭은 꽤 까다로운 것으로 알고 있습니다.

https://en.wikipedia.org/wiki/...

제가 이해한 것이 맞다면, 삼각형 두 개를 넣으면 반례가 됩니다. 정답은 5명이고 이분 매칭으로는 6명이 나옵니다.

@ssangba55

3 3

1 2

2 3

3 1

의 경우

그래프는 위와 같고, 경우에 따라 달라지겠지만, 만약 매칭이

1번친구는 3번 친구와 춤춰야하는데 막상 3번 친구는 2번 친구와 추고, 2번은 또 1번과 추게 됩니다. 마지막에 넣으신 가운데에 세울 친구를 계산하지 않더라도 매칭이 이미 3이기 때문에 해당 tc는 넘어가게 되죠.

@jh05013

이해가 잘 안되서 그런데 간단한 예시 들어주실 수 있나요??

데이터로 나타내면 아래와 같습니다.

아 겹치지 않게 삼각형을 구성하는군요.

이런 데이터 추가하면 될 것 같아요.

@jh05013 님 수고스럽겠지만 따로 게시물 작성하셔서 테케 추가해주시면 감사하겠습니다 :)

프로그래밍 문제 만드는 데 능숙한 게 아니라서 이런저런 오류하고 걸러내는 tc같은 걸 잘 못만들겟군요 ㅠ

다시 한 번 감사드립니다.

scc 냄새가 나긴 하는데.. scc를 안 짜봤으니.. ㅠㅠ