Internet connection

#include <iostream>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
#define N 1000
using namespace std;
 
vector<long long int> g[N];
map<pair<long long int, long long int>, long long int> weights;
map<pair<long long int, long long int>, long long int> flow;
 
vector<pair<long long int, long long int>> bfs(long long int s, long long int t) {
    queue<long long int> q;
    vector<bool> vis(N);
 
    map<long long int, vector<long long int>> mm;
    
    q.push(s);
    while( not q.empty()) {
        auto u = q.front();
        q.pop();
 
        if (u == t) {
            vector<pair<long long int, long long int>> res;
            while (true) {
                if (u == s) {
                    reverse(res.begin(), res.end());
                    return res;
                }
                long long int v = mm[u].front();
                res.push_back(make_pair(v, u));
                u = v;
            }
        }
 
        if (not vis[u]) {
            vis[u] = true;
            for(auto &v: g[u]) {
                if (weights[make_pair(u, v)] - flow[make_pair(u, v)] > 0 and not vis[v]) {
                    q.push(v);
                    if (mm.find(v) == mm.end()) {
                        vector<long long int> xxx = {u};
                        mm[v] = xxx;
                    }else {
                        mm[v].push_back(u);
 
                    }
                }
            }
        }
    }
    return vector<pair<long long int, long long int>>();
}
 
 
int main()
{
    long long int n, m; // n vertices, m edges
 
    // build up the
    cin >> n >> m;
 
    for (long long int i = 0; i < m; i++)
    {
        long long int v, w, c;
        cin >> v >> w >> c;
        g[v].push_back(w);
        //g[w].push_back(v);
        weights[make_pair(v, w)] = c;
    }
 
    for (long long int u = 0; u < n; u++) {
        for (size_t v = 0; v < g[u].size(); v++) {
            if (g[u][v] == 0) {
                break;
            }
            flow[make_pair(u, v)] = 0;
            flow[make_pair(v, u)] = 0;
        }
    
    }
 
 
 
    while (true) {
        auto v = bfs(1, n);
        if (v.empty()) {
            break;
        }
 
        auto smallestpair = *min_element(v.begin(), v.end(), [&](const pair<long long int, long long int> &a, const pair<long long int, long long int> &b){ return weights[a] - flow[a] < weights[b] - flow[b];});
        auto cfp = weights[smallestpair] - flow[smallestpair];
 
        for (auto &i : v) {
            auto u = i.first;
            auto v = i.second;
            flow[make_pair(u, v)] = flow[make_pair(u, v)] + cfp; 
            flow[make_pair(v, u)] = flow[make_pair(v, u)] - cfp;
        }
    }
 
    long long int s = 0;
    for (auto & gg: g[1]) {
        s += flow[make_pair(1, gg)];
    }
    cout << s << endl;
    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: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED