Internet connection

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>

unsigned long *data;
int n, m;

std::list<unsigned int> get_path(){
    unsigned int visited[n + 1];
    for(int i = 0; i <= n; i++)
        visited[i] = 0;
    
    visited[1] = 1;
    
    std::queue<unsigned int> queue({1});
    
    while(!queue.empty()){
        unsigned int v = queue.front();
        queue.pop();
        if(data[v * (n + 1) + n] > 0){
            visited[n] = v;
            break;
        }
        for(int i = 1; i <= n; i++){
            if(visited[i] == 0 && data[v * (n + 1) + i] > 0){
                visited[i] = v;
                queue.push(i);
            }
        }
    }

    
    std::list<unsigned int> result = {};
    
    if(visited[n] != 0){
        result.push_front (n);
        unsigned int last = n;
        
        while(last != 1){
            last = visited[last];
            result.push_front (last);
        }
    }
    
    return result;
}

unsigned long get_path_throughput(std::list<unsigned int> path){
    unsigned long result = ULONG_MAX;
    std::list<unsigned int>::iterator it = path.begin();
    unsigned int v1 = *it;
    it++;
    for(; it != path.end(); ++it) {
        unsigned long val = data[v1 * (n + 1) + *it];
        if(val < result){
            result = val;
        }
        v1 = *it;
    }
    return result;
}

void process_path(std::list<unsigned int> path, unsigned long throughput){
    std::list<unsigned int>::iterator it = path.begin();
    unsigned int v1 = *it;
    it++;
    for(; it != path.end(); ++it){
        //std::cout << v1 << "," << *it << std::endl;
        data[v1 * (n + 1) + *it] -= throughput;
        data[*it * (n + 1) + v1] += throughput;
        v1 = *it;
    }
}

int main(int argc, const char * argv[]) {
    
    std::cin >> n >> m;
    //std::cout << "n=" << n << " m=" << m << "\n";
    
    data = (unsigned long *)malloc((n + 1) * (n + 1) * sizeof(unsigned long));
    unsigned int a, b;
    unsigned long c;
    
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            data[i * (n + 1) + j] = 0;
        }
    }
    
    
    for(int i = 0; i < m; i++){
        std::cin >> a >> b >> c;
        //std::cout << "a=" << a << " b=" << b << " c=" << c << "\n";
        data[a * (n + 1) + b] = c;
    }
    
    /*
    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < n + 1; j++){
            std::cout << data[i * (n + 1) + j] << "\t";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
     */
    
    std::list<unsigned int> mypath;
    unsigned long total_throughput = 0;
    do{
        mypath = get_path();
        
        /*
        std::cout << "path  \n";
        for (std::list<unsigned int>::const_iterator i = mypath.begin(); i != mypath.end(); ++i)
            std::cout << *i << ' ';
        std::cout << "\n";
         */
        
        if(!mypath.empty()){
            unsigned long throughput = get_path_throughput(mypath);
            total_throughput += throughput;
            //std::cout << "throughput " << throughput << std::endl;
            
            process_path(mypath, throughput);
            
            /*
            for(int i = 0; i < n + 1; i++){
                for(int j = 0; j < n + 1; j++){
                    std::cout << data[i * (n + 1) + j] << "\t";
                }
                std::cout << "\n";
            }
            std::cout << "\n";
             */
        }
      
        
    } while (!mypath.empty());
    
    
    std::cout << total_throughput << "\n";
    
    return 0;
}

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