사용자 도구

사이트 도구


ps:problems:boj:12843

복수전공

ps
링크acmicpc.net/…
출처BOJ
문제 번호12843
문제명복수전공
레벨플래티넘 3
분류

이분 매칭, 최대 독립집합

시간복잡도O(VE)
인풋사이즈V<=2000, E<=2,000,000
사용한 언어Python
제출기록60052KB / 1052ms
최고기록1052ms
해결날짜2022/03/16

풀이

  • 강의를 노드로, 겹치는 관계를 엣지로 연결해주자. 다른 학부의 강의들 사이에서만 엣지가 존재하기 때문에 이분 그래프가 된다.
  • 겹치지 않는 강의들을 최대한 많이 고르는 것은 최대 독립집합을 구하는 문제가 되고, 전체 노드 갯수에서 최소 버텍스 커버의 크기를 빼주면 최대 독립집합의 크기를 구할수 있다. 이분그래프이기 때문에 쾨닉의 정리에 따라서 최소 버텍스 커버의 크기는 최대 매칭의 크기와 같다. 결국 답은 n에서 이분매칭의 크기를 빼주면 된다.
  • 시간복잡도는 이분 매칭 (Bipartite Matching)을 구하는데에 O(VE)가 걸린다.

코드

"""Solution code for "BOJ 12843. 복수전공".

- Problem link: https://www.acmicpc.net/problem/12843
- Solution link: http://www.teferi.net/ps/problems/boj/12843

Tags: [Bipartite Matching]
"""

import sys
from teflib import tgraph


def main():
    # pylint: disable=unused-variable
    n, m = [int(x) for x in sys.stdin.readline().split()]
    bigraph = [[] for _ in range(n)]
    comp_lectures = set()
    for _ in range(n):
        lecture, dep = sys.stdin.readline().split()
        if dep == 'c':
            comp_lectures.add(int(lecture))
    for _ in range(m):
        lecture1, lecture2 = [int(x) for x in sys.stdin.readline().split()]
        if lecture1 in comp_lectures:
            bigraph[lecture1 - 1].append(lecture2 - 1)
        else:
            bigraph[lecture2 - 1].append(lecture1 - 1)

    print(n - len(tgraph.bipartite_matching(bigraph)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
H T᠎ M G N
 
ps/problems/boj/12843.txt · 마지막으로 수정됨: 2022/03/16 10:31 저자 teferi