사용자 도구

사이트 도구


ps:problems:boj:2051

최소 버텍스 커버

ps
링크acmicpc.net/…
출처BOJ
문제 번호2051
문제명최소 버텍스 커버
레벨플래티넘 2
분류

이분 매칭

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

풀이

  • 이분 그래프에서 최소 버텍스 커버를 구하는 문제.
  • 이분 그래프에서 최대 매칭의 크기와 최소 버텍스 커버의 크기가 같다는 쾨닉의 정리는 많이 쓰이지만, 최소 버텍스 커버의 원소들을 실제로 구하는 것이 필요한 문제는 흔하지는 않다.. 최소 버텍스 커버 원소들을 구하는 방법은 최소 버텍스 커버 구하기 참고
  • 시간복잡도는 이분매칭에 O(VE), 그리고 그 결과를 이용해서 최소 버텍스 커버를 구하는 데에 다시 O(VE)가 든다. 총 O(VE).

코드

"""Solution code for "BOJ 2051. 최소 버텍스 커버".

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

Tags: [Bipartite Matching]
"""

from teflib import tgraph


def minimum_vertex_cover(bigraph):

    def dfs_rec(u, is_mvc):
        is_mvc[u] = False
        for v in bigraph[u]:
            if not is_mvc[v]:
                is_mvc[v] = True
                if (next_u := matched_node[v]) is not None and is_mvc[next_u]:
                    dfs_rec(next_u, is_mvc)

    matching = tgraph.bipartite_matching(bigraph)
    matched_node = [None] * len(bigraph)
    for u, v in matching.items():
        matched_node[v] = u
    is_mvc = [bool(edges) for edges in bigraph]
    for u, edges in enumerate(bigraph):
        if edges and u not in matching:
            dfs_rec(u, is_mvc)
    return [u for u, u_is_mvc in enumerate(is_mvc) if u_is_mvc]


def main():
    N, M = [int(x) for x in input().split()]
    bigraph = [[] for _ in range(N + M)]
    for i in range(N):
        _, *j = [int(x) for x in input().split()]
        bigraph[i] = [x + N - 1 for x in j]

    mvc = minimum_vertex_cover(bigraph)
    answer1 = [u + 1 for u in mvc if bigraph[u]]
    answer2 = [v - N + 1 for v in mvc if not bigraph[v]]

    print(len(mvc))
    print(len(answer1), *answer1)
    print(len(answer2), *answer2)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F W Z᠎ T O
 
ps/problems/boj/2051.txt · 마지막으로 수정됨: 2022/03/16 10:20 저자 teferi