IMPA/p11506/p11506.cpp

#include <iostream>
#include <utility>
#include <list>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

struct Edge;

struct Node
{
    Node(){}
    Node(unsigned int size):neighbours{size} {}

    int id;
    int capacity;

    vector<struct Edge*> neighbours;
};

struct Edge
{
    Edge(Node *n1, Node *n2, int cap):n1{n1}, n2{n2}, flow{0}
    {
        capacity = min(min(n1->capacity, n2->capacity), cap);

        n1->neighbours.push_back(this);
        n2->neighbours.push_back(this);
    }

    Node *n1, *n2;
    int capacity;
    int flow;
};

Node *other_node(Edge *e, Node *curr)
{
    if(e->n1 == curr)
        return e->n2;

    return e->n1;
}

int edmonds_karp(vector<Node> &m, Node *source, Node *sink)
{
    int max_flow = 0;
    // Göra bra krejjer
    Edge *es = new Edge(source, source, 200000);
    while(true)
    {
        vector<Edge*> parent(m.size()+1, nullptr);

        queue<Node*> q;
        q.push(source);
        parent[source->id] = es;

        while(!q.empty())
        {
            Node *curr = q.front();
            q.pop();

            for(auto e : curr->neighbours)
            {
                Node *o = other_node(e, curr);
                if(parent[o->id] == nullptr && e->capacity > e->flow)
                {
                    q.push(o);
                    parent[o->id] = e;
                }
            }
        }


        // No (new) way to sink
        if(parent[sink->id] == nullptr)
            break;

        int push_flow = 200000;

        Edge *e = parent[sink->id];
        Node *curr = sink;
        while(curr != source)
        {
            push_flow = min(push_flow, (e->capacity - e->flow) );

            curr = other_node(e, curr);
            e = parent[curr->id];
        }


        e = parent[sink->id];
        curr = sink;
        while(curr != source)
        {
            e->flow += push_flow;

            curr = other_node(e, curr);
            e = parent[curr->id];
        }

        max_flow += push_flow;
    }

    delete es;

    return max_flow;
}

int main()
{
    int num_machines, num_wires;

    while(cin >> num_machines >> num_wires)
    {
        if(!num_machines && !num_wires)
        {
            break;
        }

        vector<Node> machines(num_machines);
        machines[0].id = 1;
        machines[0].capacity = 200000;
        machines[num_machines-1].id = num_machines;
        machines[num_machines-1].capacity = 200000;

        for(int i = 0; i < num_machines-2; i++)
        {
            int id, capacity;
            cin >> id >> capacity;
            machines.at(id-1).id = id;
            machines.at(id-1).capacity = capacity;
        }

        for(int i = 0; i < num_wires; i++)
        {
            int node1, node2, capacity;
            cin >> node1 >> node2 >> capacity;
            node1--;
            node2--;

            Node *n1 = &machines[node1];
            Node *n2 = &machines[node2];

            new Edge(n1, n2, capacity);
        }


        cout << edmonds_karp(machines, &machines[0], &machines[num_machines-1]) << endl;

        for(auto m : machines)
        {
            cout << m.id << ":" << m.capacity << endl;
            for(auto n : m.neighbours)
            {
                cout << "\t" << n->n1->id << " <--> " << n->n2->id << "  Cap: " << n->capacity << "   Flow: " << n->flow << endl;
            }
        }

    }

    return 0;
}