gistfile1.txt

#include <vector>
#include <cassert>
#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>

class Network {
public:
    size_t NumNodes() const { return nodes_.size(); };
    size_t NumEdges(size_t node) const { return nodes_[node].size(); };
    
    size_t EdgeDst(size_t node, size_t edge) const{
        return nodes_[node][edge].dst;
    }
    
    int EdgeCapacity(size_t node, size_t edge) const{
        Edge e = nodes_[node][edge];
        return e.absolute_capacity - e.flow;
    }
    
    int EdgeFlow(size_t node, size_t edge) const {
        return nodes_[node][edge].flow;
    }
    
    void PushFlow(size_t node, size_t edge, int flow) {
        Edge& e = nodes_[node][edge];
        e.flow -= flow;
        assert(e.flow <= e.absolute_capacity);
        nodes_[node][edge].flow -= flow;
    }
    
    void AddEdge(size_t from, size_t to, int capacity){
        if (nodes_.size() <= std::max(from, to)) {
            nodes_.resize(std::max(from, to)+1);
        }        


    }
private:
    struct Edge {
        size_t dst, twin;
        int flow, absolute_capacity;
    };
    
    std::vector<std::vector<Edge>> nodes_;
};

void TestNetwork() {
    Network n;

    n.AddEdge(5, 10, 1);
    n.AddEdge(5, 7, 4);
    n.AddEdge(7, 5, 3);

    assert(n.NumNodes() == 11);
    assert(n.NumEdges(5) == 3);
    assert(n.NumEdges(10) == 1);
    assert(n.NumEdges(7) == 2);

    assert(n.EdgeCapacity(5, 1) == 4);
    assert(n.EdgeFlow(5, 1) == 0);
    assert(n.EdgeCapacity(7, 0) == 0);
    assert(n.EdgeFlow(7, 0) == 0);

    n.PushFlow(5, 1, 3);

    assert(n.EdgeCapacity(5, 1) == 1);
    assert(n.EdgeFlow(5, 1) == 3);
    assert(n.EdgeCapacity(7, 0) == 3);
    assert(n.EdgeFlow(7, 0) == 0);
}


typedef std::vector<std::pair<size_t, size_t>> Path;

bool FindPath(const Network& network, Path* path, size_t start, size_t end) {
    std::vector<size_t> back_node(network.NumNodes(), -1);
    std::vector<size_t> back_edge(network.NumNodes());
    
    std::deque<size_t> queue;
    queue.push_back(start);
    back_node[start] = start;
    while (!queue.empty()) {
        size_t node =queue.front();
        queue.pop_front();
        
        for (size_t edge = 0; edge < network.NumEdges(node); ++edge) {
            if (network.EdgeCapacity(node, edge) == 0) continue;
            
            size_t to = network.EdgeDst(node, edge);
            if (back_node[to] != -1) continue;
            queue.push_back(to);
            back_node[to] = node;
            back_edge[to] = edge;
            
        }
        
    }
    
    if (back_node[end] == -1) return false;
    path->clear();
    for (size_t node = end; node != start; node = back_node[node]) {
        path->emplace_back(back_node[node], back_edge[node]);
    }
    return true;
}

void MaxFlow(Network* network, size_t source, size_t sink){
    Path path;
    while (FindPath(*network, &path, source, sink)){
        int min_capacity = network->EdgeCapacity(path[0].first, path[0].second);
        for(const auto& edge : path){
            min_capacity = std::min(min_capacity, network->EdgeCapacity(edge.first, edge.second));
        }
        for(const auto& edge : path){
            network->PushFlow(edge.first, edge.second, min_capacity);
        }
    }
}

int main() {
    TestNetwork();
    return 0;
}