rupitere   7년 전

네트워크 플로우 공부하면서 문제를 풀어보려고 노력하고 있는데 어떤 방식으로 접근해야하는지 감이 잘 안와서요

f2ad4e234951e6d6368c158cb4d735f3.png

문제의 예제를 위 그림의 그래프처럼 생각했는데 맞는지 궁금합니다.

그리고 어떻게 접근해야 할지 간단한 힌트만 이라도 주시면 감사할게요ㅠㅠㅠ

또 이문제를 네트워크 플로우 문제로 어떻게 생각하고 보는건지도 혹시 아시는분 있으시면 알려주세요ㅠㅠ 몇주동안 틈틈히 했는데 개념을 몰라서 그런지 못푸네요ㅠㅠ

pl0892029   7년 전

이 문제가 최소 꼭지점 덮개 유형임을 아시면 좋겠네요.

그리고 최소 꼭지점 덮개의 꼭지점의 수는 이분 그래프 형태일 경우에는 최대 매칭 수와 동일합니다.(https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))

제가 잘못 알고 있는데 있으면 다른 분들꼐서 아래 댓글로 부연설명이나 정정부탁드려요.

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