백준 1536번 Dance, Dance

개인적으로 정확한 그래프 모델링을 하기 어려웠습니다 ㅠㅠ

제가 아직 플로우에 좀 약해서 좀 어려웠네요

처음에 짠 그래프 모델링을 갈아엎고 또 갈아엎고 하다 결국 AC 를 맞았습니다 흑흑 ㅠㅠ

solved.ac 기준으로 플레4 이던데 다른 유량 문제들 티어에 비교하면 플레1은 족히 받아야 하지 않나 싶습니다.

 

일단 최대 라운드는 $ N $ 번까지가 최대이라는 것을 알 수 있습니다.

즉 $ x $ 번 라운드까지 갈 수 있다는 것은 그래프 모델링을 하고 유량을 흘려줬을 때 유량 값이 $ x*n $이면 갈 수 있다는 것을 의미합니다.

 

$ x $ 번 라운드가 가능한지 볼 때 그래프모델링을 잘 해줘서 유량을 판단하는 문제라고 할 수 있습니다.

 

그래프 모델링을 하는 방법은 $ S $ 에서 각각 $ 1 $ ~ $ N $ 까지 $ x $ 만큼 유량을 흘려줍니다.

그리고 $ 1 $ ~ $ N $ 에서 두 가지로 나뉘게 됩니다 

첫 번째로는 좋아하는 사람에게만 가는 유량, 싫어하는 사람에게만 가는 유량

좋아하는 사람에게만 가는 유량은 좋아하는 사람의 명수만큼 유량을 흘려주면 되고

싫어하는 사람에게만 가는 유량은 $ k $ 만큼 흘려주면 됩니다.

 

반대쪽도 똑같이 방금과 말한대로 짭니다 ( 당연히 반대쪽은 여자버젼 그래프입니다 )

 

그리고 남자 여자 좋아하는 유무를 따져서 남자 그래프 여자 그래프 사이를 이어주면 됩니다.

 

밑에는 예제 그래프입니다.

 

m : 남자 g : 여자  l : 좋아한다 h : 싫어한다