secondcow   3년 전

임의의 한 자리(r, c)와 컨닝관계를 그래프로 표현할 때

- 틀린 그래프 : (r-1, c-1) (r, c-1) (r-1, c+1) (r, c+1) 하고만 간선 생성

- 정답 그래프 : 위 간선 + (r+1, c-1) (r+1, c+1)까지 총 6개 생성

반례)

1

3 3

...

...

x.x

오답 : 5 답 : 4

밑에 까지 컨닝관계를 간선으로 잇지 않으면

마지막 최대매칭이 보장되지 않을 수 있다

(구현 상에서 짝수 열만 매칭을 시도해서 그런 것같음..)


sontg123   3년 전

 이거랑 완저니 같은 케이스로 왜안되는지 한참 고민했네요 이분매칭은 뭔가 단방향그래프로만 생각해서 이런생각을 못했습니다.. 넘넘감사합니다

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