IMPA/p11506/p11506.cpp

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

using namespace std;

struct Edge;

struct Node
{
    Node():flow{0} {}
    Node(unsigned int size):flow{0}, neighbours{size} {}

    int id;
    int capacity;
    int flow;

    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)
{
    // Edmonds karp-variant
    int max_flow = 0;

    // Lägg in en båge från source till sig själv för att undvika specialfall
    Edge *es = new Edge(source, source, 200000);

    // Medan vi inte har hittat alla intressanta vägar från source till sink
    while(true)
    {
        // Förbered vektor att spara alla bågar vi gått till respektive nod
        vector<Edge*> parent(m.size()+1, nullptr);

        // Kö för bredden först
        queue<Node*> q;
        q.push(source);
        parent[source->id] = es; // Lägg in special-bågen för source

        // Bredden först typ
        while(!q.empty())
        {
            Node *curr = q.front();
            q.pop();

            for(auto e : curr->neighbours)
            {
                // Pekare till noden o på andra sidan bågen e
                Node *o = other_node(e, curr);
                if(parent[o->id] == nullptr && e->capacity > e->flow && o->capacity > o->flow)
                {
                    // Ifall vi inte gått vägen innan, och den fortfarande har kapacitet kvar
                    // Lägg till noden till bredden först
                    q.push(o);
                    // och spara bågen vi tog för att hamna i nuvarande nod
                    parent[o->id] = e;
                }
            }
        }


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

        int push_flow = 200000; // INT_MAX funkade inte :(

        // Gå igenom eld och vatten
        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);

            curr->flow += push_flow;

            e = parent[curr->id];
        }

        max_flow += push_flow;
    }

    delete es;

    return max_flow;
}

int main()
{
    int num_machines, num_wires;
    int test = 1;
    while(cin >> num_machines >> num_wires)
    {
        if(!num_machines && !num_wires)
        {
            break;
        }

        vector<Node> machines(num_machines);
        vector<Edge*> edges(num_wires);

        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);
            //edges[i] = 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;
//            }
//        }

//        if(test++ == 58000)
//        {
//            cout << num_machines << " " << num_wires << endl;
//            for(auto m : machines)
//            {
//                cout << m.id << " " << m.capacity << endl;
//            }
//            for(auto e : edges)
//            {
//                cout << e->n1->id << " " << e->n2->id << " " << e->capacity << endl;
//            }
//        }

    }

    return 0;
}