반응형 Networkflow1 [백준/C++] 6086번 - 최대 유량 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 network Flow문제와 같다. 같은 지점에서 같은 지점으로 연결된 관은 병렬연결이므로 흐를 수 있는 유량에 더해준다. 그리고 양방향으로 흐를 수 있다고 했으므로 이 점도 고려해 흐를 수 있는 유량에 더해주면, Network Flow 문제가 된다. Network Flow 문제를 푸는 방법을 간단하게 소개하면 1. 유량 보존의 법칙 유체가 나오는 부분을 source, 들어오는 부분을 sink라고 하는데, 이 두 부분을 제외하고는 각 정점에서 들어오는 유량과 나가는 유량이 일치해야 한다. 2. 유량의 대칭성 f(u, v) = A 가 u에서 v로 A 만큼 유체가 흐르는 것을 의미한다고 하자. 그러면 .. 2024. 2. 5. 이전 1 다음 반응형