deneb2016   2달 전

플로우 문제집에 들어있던데, 대체 어떻게 유량 그래프를 만들어야 할지 도저히 모르겠네여.. ㅠ

고양이를 좋아하는 그룹 내의 사람들끼리는 모순(둘 중 한 명의 의견은 무시당해야만 하는 경우)이 생길 일이 없고,

개를 좋아하는 그룹 내의 사람들끼리는 모순이 생길 일이 없습니다.

따라서 고양이를 좋아하는 그룹/개를 좋아하는 그룹으로 나눈 뒤 서로 양립할 수 없는 사람들 간에만 간선을 이어서 이분 그래프를 만듭니다.

이때 이 이분 그래프에서 간선, 즉 매칭은 의견의 충돌 1회를 의미합니다.

의견의 충돌을 모두 없애기 위해서는 어떤 매칭도 남지 않게 되면 되겠네요.

어떤 매칭도 남지 않는다는 것은 해당 이분 그래프로 네트워크를 구성했을 때 유량이 더이상 흐를 수 없다는 것과 동치가 됩니다.

유량이 흐를 수 없도록 해야 한다? 네. 네트워크에 대한 컷을 구하는 문제로 바뀌게 됩니다. 

컷에 속한 간선 하나당 해당 간선 양 끝점의 두 사람 중 한 사람의 의견을 무시하는 것과 같다고 생각하시면 됩니다.

우리는 무시당하는 인원을 최소화하고 싶네요. 그럼 컷 중에서도 민컷을 구하면 됩니다. 민컷 = 최대유량 = 최대 매칭이므로,

총 시청자 수에서 해당 이분 그래프에서의 최대 매칭을 빼 주면 답이 됩니다.

deneb2016   2달 전

와.. 최소컷이란 개념을 잠시 까먹고 있었네요...

정말 감사합니다.

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