mmpj   1년 전

1587 이분매칭 문제 이해가 잘 안되어 질문드립니다.

예제입력의 답이 6 이라고 하는데

A---B

1---5

3---6

4---2

이렇게 1-5, 3-6, 4-2 를 연결하는 간선 3개 나오는거 아닌가요?

6 이 어떻게나오는건가요??

그리고 문제에서

간선의 끝 점은 A에 하나, B에 하나 있어야 한다.

라고 했는데

Ai에서 Ai+1로 가는 간선 (1<=i<=nA-1)과 Bi에서 Bi+1로 가는 간선 (1<=i<=nB-1)

은 왜 주어지는건가요?

어차피 A 안에 점들끼리, B 안에 점들끼리는 연결 못하는거 아닌가요?

algoshipda   1년 전

이 문제는 이분그래프가 아니고 A안의 점들끼리 B안의 점들끼리도 이을 수 있어요

algoshipda   1년 전

fbc144d478848502fcf17ef9759fdea0.png

mmpj   1년 전

어떻게 6이 나오는건지 조금만 더 자세히 설명부탁드립니다. ㅠ

그럼 A 에서 1-2, 3-4, 5-6, 3개, B 에서 1-2, 3-4, 5-6, 3개, 이렇게 6개가 나오는건가요?

그럼 예제입력에

4

1 3

1 5

3 6

4 2

은 왜 주어지는건가요?

algoshipda   1년 전

6 6 이면 A그룹 6개 있고 B그룹 6개 있습니다. 기본적으로 각 그룹은 문제에서 말한대로 간선이 이어져있고요 밑에 주어지는건 추가적인 간선입니다.

4

1 3

1 5

3 6

4 2

는 왼쪽 숫자는 A그룹에 있는 정점이고 오른쪽 숫자는 B그룹에 있는 정점이고 저대로 그리면 위 그림처럼 나와요. 빨갛게 표시한게 매칭이구요

mmpj   1년 전

감사합니다. 얼핏 이해된 것 같습니다.

appa   1년 전

좋은 문제네요.

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