[주의] 그냥 끄적거린 글입니다.
LR flow 에 대해서 공부를 해보았습니다
방법에 대해선 구글에 많으니 생략하고 유의할 점에 대해서 적어보겠습니다.
일반적으로 LR Flow에는 demand 값이라고 이 정점을 지나가는 유량에 대한 정보가 있습니다.
이 demand 값을 잘 설정해줘야 한다는 것입니다.
즉 demand 가 없고 간선의 하한 상한만 존재하는 그래프에선 알아서 잘 circulation 하게 그래프를 만들어줘야 한다는 점입니다. (초기 그래프의 demand 값이 0이 되도 상관 없기 때문입니다 )
아니면 정점에 demand 값을 알맞게 배분해주는 방법도 있겠지만 이 경우는 반례가 생길 수도 있고 위험합니다.
circulation 하게 그래프를 만드는 방법에 대해서 잘 모르겠긴 하지만 일반적으로 소스 싱크가 있는 그래프에선 싱크 -> 소스로 무한대의 값의 플로우를 흘려주면 됩니다.
'공부일기장' 카테고리의 다른 글
앳코더 옐로 복귀! (0) | 2021.04.18 |
---|---|
요즘 PS 하면서 느꼈던 것들...... 후.. (0) | 2021.03.14 |
오늘 혹독한 디버깅을 하면서 배운 점 (0) | 2020.10.06 |
Scpc2020 1차 예선 때 일기 (0) | 2020.08.23 |
19.12.17 (0) | 2019.12.17 |