luluctrl4   7년 전

전체 개수에서 이분매칭 값을 거꾸로 빼니까 답이 나오는거 같네?

해서 제출해봣더니 맞았는데

생각해봐도 왜 아직도 답인지 모르겠어요

WeissBlume   7년 전

각 자리를 정점으로 놓고 서로 컨닝을 할 수 있는 자리끼리 간선을 이어줍시다.
이제 이 그래프에서 서로 인접하지 않은 정점을 고르되, 그 개수가 최대가 되게 합시다(이를 maximum indepenedent set[3])이라 합니다.
maximum independent set은 minimum vertex cover[2]의 complement입니다(그래서 |V| - |VC| = |IS| 입니다).
그런데 잘 보면 이 그래프는 이분 그래프입니다. 이분 그래프에서의 minimum vertex cover는 maximum matching과 같습니다[1].

---------------------------------------------------------------------------------------------------------------
[1]: https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)
[2]: https://en.wikipedia.org/wiki/Vertex_cover
[3]: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

luluctrl4   7년 전

@WeissBlume

오.. 감사합니다

댓글을 작성하려면 로그인해야 합니다.