Download Speed

Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?

Example:

Input:  n = 4, m = 5, edges = {{1, 2, 3}, {2, 4, 2}, {1, 3, 4}, {3, 4, 5}, {4, 1, 3}}
Output: 6

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1LL << 62;

vector<tuple<long long, long long, long long>> adj[505];
long long xpow(long long x, unsigned long long y)
{
    long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x);
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
long long d, n;
bool vis[505];
long long dfs(long long s, long long f)
{
    if (s == n)
        return f;
    vis[s] = 1;

    for (auto &[i, w, j] : adj[s])
    {
        if (w >= d && !vis[i])
        {
            long long b = dfs(i, min(f, w));
            if (b > 0)
            {
                w -= b;
                get<1>(adj[i][j]) += b;
                return b;
            }
        }
    }
    return 0;
}
long long downloadSpeed(long long m,
                        vector<vector<long long>> &edges)
{

    long long mx = 0;
    for (long long i = 0; i < m; i++)
    {
        long long x = edges[i][0];
        long long y = edges[i][1];
        long long w = edges[i][2];

        mx = max(mx, w);
        long long j1 = adj[x].size();
        long long j2 = adj[y].size();
        adj[x].push_back({y, w, j2});
        adj[y].push_back({x, 0, j1});
    }
    d = xpow(2, (long long)log2(mx));
    long long ans = 0;
    while (d > 0)
    {
        while (1)
        {
            memset(vis, 0, sizeof vis);
            long long f = dfs(1, inf);
            ans += f;
            if (f == 0)
                break;
        }
        d >>= 1;
    }
    return ans;
}
int main()
{
    n = 4;
    long long m = 5;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 4, 2},
                                       {1, 3, 4},
                                       {3, 4, 5},
                                       {4, 1, 3}};

      cout << downloadSpeed(m, edges) << "\n";

    return 0;
}