본문 바로가기

포드-폴커슨 알고리즘

[알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 12. 27. [알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java) 네트워크 유량 그래프 문제에는 경로의 길이 외에도 그래프에 대해 정의할 수 있는 중요한 개념이 있다. 바로 그래프의 ‘용량’이다. 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 ‘흐름’ 혹은 ‘유량’을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 부른다. 교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실에서 자주 찾을 수 있는 문제들이다. 또한 네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다. 유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 추..
[BOJ] 백준 6086번 최대 유량 (Java)
Dot Algo∙ DS/PS 2021. 12. 27. [BOJ] 백준 6086번 최대 유량 (Java) #6086 최대 유량 난이도 : 플레 4 유형 : 네트워크 유량 / 포드-폴커슨 알고리즘 / 최대 유량 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net ▸ 문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. ..

티스토리툴바

티스토리툴바