네트워크 플로우2 [알고리즘 정리]네트워크 플로우(Network Flow) 알고리즘_에드몬드 카프 알고리즘(Edmonds-Karp algorithm) 네트워크 플로우 코드적으로 이해하는것이 조금 어려울 수 있지만, 개념자체는 간단하게 "도착지(Sink)에 얼마나 물이 나오게 할 수 있느냐?"에 관한 문제입니다. 그림을 보면 쉽게 이해 할 수 있다. 위의 문제에서 각 Source와 각 수도관은 주어진 리터만큼 시간당 물을 보낼 수 있고 하였을때, Sink에는 시간당 얼만큼의 물이 도달 할 수있냐? 딱, 봐도 8L의 물이 도달 할 수 있다는 것을 알 수 있다. 이 문제를 해결 하는 것이 네트워크 플로우다. 용어 정리 & 주요 특징 - (용어 1) Source : 네트위크(물)의 시작점 - (용어 2) Sink: 네트워크(물)의 도착지점 - (용어 3) c(a,b) : a->b로 흐를 수 있는 물의 최대량(용량) - (용어 4) f(a,b) : a->b로 .. 2018. 10. 3. 백준(BOJ) 2316 도시 왕복하기 *** # 네트워크 플로우 # 최대 유량 #include #include #include #include using namespace std; typedef struct st { int from; int to; vector pre; }ho; int n,m,a,b,st=1,fi=2,use[405][405],ans=0; bool tf=true; vector v[405]; queue q; int main() { scanf("%d%d",&n,&m); for(int i=0;i 2018. 10. 1. 이전 1 다음
