Internet connection

#include <iostream>
#include <queue>
#include <vector>
#define index(source, sink) ((source * amountNodes) + sink)
#define MAX_CAPACITY 1000000000

using namespace std;


int amountNodes, amountEdges;
long totalFlow;

bool bfs(int capacities [], int flows [], vector<int> neighbours [], int predecesor []) {
    int currentNode;

    queue<int> queueNodesToCheck;
    queueNodesToCheck.push(0);
    
    fill_n(predecesor, amountNodes, -1);

    while(!queueNodesToCheck.empty()) {
        currentNode = queueNodesToCheck.front(); 
        queueNodesToCheck.pop();
        for(int neighbourNode: neighbours[currentNode]) {
            if(neighbourNode != 0 && predecesor[neighbourNode] == -1 && capacities[index(currentNode, neighbourNode)] > flows[index(currentNode, neighbourNode)]) {
                predecesor[neighbourNode] = currentNode;
                queueNodesToCheck.push(neighbourNode);


                // cout << currentNode;
                // cout << " currentNode\n";

                // cout << neighbourNode;
                // cout << " neighbourNode\n";

            }
        }
        if(predecesor[amountNodes-1] != -1){
            break;
        }
    }
    // cout << predecesor[amountNodes-1];
    // cout << " pred sink\n";
    return predecesor[amountNodes-1] != -1;
}


void increaseFlow(int capacities [], int flows [], int predecesor []) {
    //get flow amount
    int currentNode = amountNodes-1;
    int df = MAX_CAPACITY;
    int nextNode = predecesor[currentNode];
    while(nextNode != -1) {
        df = min(df, capacities[index(nextNode, currentNode)] - flows[index(nextNode, currentNode)]);
        
        // cout << currentNode;
        // cout << " currentNode\n";
        // cout << nextNode;
        // cout << " nextNode\n";
        // cout <<  predecesor[nextNode];
        // cout << "  predecesor[nextNode]\n";


        currentNode = nextNode;
        nextNode = predecesor[currentNode];
    }
    if(df < 0) {
        //cout << df;
        cout << '\n';
    }

    currentNode = amountNodes-1;
    nextNode = predecesor[currentNode];

    while(nextNode != -1) {
        flows[index(nextNode, currentNode)] += df;
        flows[index(currentNode, nextNode)] -= df;
        currentNode = nextNode;
        nextNode = predecesor[currentNode];
    }
    totalFlow += df;
}

long edmondsKarp(int capacities [], int flows [], vector<int> neighbours []) {
    int * predecesor = new int [amountNodes];
    totalFlow = 0;
    while(bfs(capacities, flows, neighbours, predecesor)) {
        increaseFlow(capacities, flows, predecesor);
    }

    return totalFlow;

}




int main() {
    cin >> amountNodes >> amountEdges;
    vector<int> neighbours [amountNodes];

    int * capacities = new int [amountNodes*amountNodes];
    int * flows = new int [amountNodes*amountNodes];

    fill_n(capacities, amountNodes*amountNodes, 0);
    fill_n(flows, amountNodes*amountNodes, 0);

    int source, sink, cap;
    for(int edgeId = 0; edgeId < amountEdges; edgeId++ ) {
        cin >> source >> sink >> cap;
        source--;sink--;
        neighbours[source].push_back(sink);
        neighbours[sink].push_back(source);
        capacities[index(source, sink)] = capacities[index(sink, source)] = flows[index(sink, source)] = cap;
    }


    cout << edmondsKarp(capacities, flows, neighbours) << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED