네트워크 유량

현실세계의 인터넷이라고 가정하자.

서버 s에서 집 컴퓨터 t까지 경로가 여러개 있고, 각각의 경로에는 보낼수 있는 최대한의 대역폭이 있다.

집 컴퓨터 t에서 자료를 다운로드받는다고 하면 s에서 보낼 수 있는 대역폭의 최대량은 얼마일까? 

(받는 쪽에서는 들어오는 만큼 다 받을수 있다고 가정한다.) 를 구하는 문제이다.

역시나 설명 잘된 블로그 : http://kks227.blog.me/220796029558

1. s에서 t로 최대한 보낼 수 있는 대역폭의 양은 얼마일까? 

아주 잠깐 살펴보면 (D에서 T로 가는) 2 + (E에서 T로 가는) 5 인 7이 일단 보이는 최대값임을 알수 있다.

하지만 만약 E로 도달할수 있는 길이 C에서 E하나뿐이고, C->E 대역폭이 4라면 E->T 대역폭이 5라도

최대 대역폭은 2+4 = 6이 될것이다. 어떻게 분배했을때 최대치가 되는지를 찾는 문제이다.

2. 위로만 보냈을경우의 예시이다.

3. 중간으로도 보내면 D->T의 대역폭이 2/2가 된다.

4. 아래로도 보내고, 요렇게 보낼 경우 최대 대역폭이 된다.

* 당연한 얘기지만 보낼 수 있는 데이터는 대역폭을 넘어서는 안된다.

* 역방향으로 대역폭이 올 경우 -로 취급한다.

기본 소스코드.

#include<cstdio>
#include<iostream>
#include<vector>
#include <queue>
using namespace std;

const int MAX_V = 100;

int V;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];

int networkFlow(int source, int sink) {
  memset(flow, 0, sizeof(flow));
  int totalFlow = 0;

  while(true) {
    vector<int> parent(MAX_V, -1);
    queue<int> q;
    parent[source] = source;
    q.push(source);
    while(!q.empty()) {
      int here = q.front(); q.pop();
      for(int there = 0; there < V; ++there)
        if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
          q.push(there);
          parent[there] = here;
        }
    }
    if(parent[sink] == -1) break;
    int amount = 987654321;
    for(int p = sink; p != source; p = parent[p])
      amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
    for(int p = sink; p != source; p = parent[p]) {
      flow[parent[p]][p] += amount;
      flow[p][parent[p]] -= amount;
    }
    totalFlow += amount;
  }

  return totalFlow;
}

int main() {
    int E;
    cin >> V >> E; //V는 정점의 갯수, E는 대역폭의 갯수
    memset(capacity, 0, sizeof(capacity)); 
    for(int i = 0; i < E; ++i) {
      int a, b, c;
      cin >> a >> b >> c; //a에서 b까지가는데 c의 대역폭이 있다.
      capacity[a][b] = c;
    }
    cout << networkFlow(0, V-1) << endl;
    for(int i = 0; i < V; ++i)
      for(int j = 0; j < V; ++j)
        if(flow[i][j] > 0)
          cout << i << " => " << j << ": " << flow[i][j] << endl;
}