Tulkki

input/code.cpp: In lambda function:
input/code.cpp:62:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |             auto [u, flow] = q.front(); q.pop();
      |                  ^
input/code.cpp: In lambda function:
input/code.cpp:178:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |                 for (; iter[u] < adj[u].size(); ++iter[u]) {
input/code.cpp: In function 'int main()':
input/code.cpp:348:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  348 |     for (int ni = 0; ni < nValues.size(); ++ni) {
      |                      ~~~^~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;
using namespace std::chrono;

// -----------------------------
// Graph Representation (Adjacency List with Capacity)
// -----------------------------
class FlowGraph {
public:
    int n;
    vector<vector<long long>> capacity;
    vector<vector<int>> adj;

    FlowGraph(int vertices) : n(vertices) {
        capacity.assign(n, vector<long long>(n, 0));
        adj.assign(n, vector<int>());
    }

    void addEdge(int u, int v, long long cap) {
        if (capacity[u][v] == 0) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        capacity[u][v] += cap;
    }

    // Reset residual graph for reuse
    void reset() {
        for (int u = 0; u < n; ++u) {
            for (int v : adj[u]) {
                capacity[u][v] = 0;
            }
            adj[u].clear();
        }
    }
};

// -----------------------------
// 1. Edmonds-Karp (Ford-Fulkerson with BFS)
// -----------------------------
long long edmondsKarp(FlowGraph& graph, int source, int sink) {
    int n = graph.n;
    vector<vector<long long>> residual = graph.capacity;
    vector<int> parent(n);
    long long maxFlow = 0;

    auto bfs = [&]() -> long long {
        fill(parent.begin(), parent.end(), -1);
        queue<pair<int, long long>> q;
        q.push({source, LLONG_MAX});
        parent[source] = -2;

        while (!q.empty() && parent[sink] == -1) {
            auto [u, flow] = q.front(); q.pop();
            for (int v : graph.adj[u]) {
                if (parent[v] == -1 && residual[u][v] > 0) {
                    parent[v] = u;
                    long long newFlow = min(flow, residual[u][v]);
                    if (v == sink) {
                        return newFlow;
                    }
                    q.push({v, newFlow});
                }
            }
        }
        return 0;
    };

    while (true) {
        long long flow = bfs();
        if (flow == 0) break;

        maxFlow += flow;
        int v = sink;
        while (v != source) {
            int u = parent[v];
            residual[u][v] -= flow;
            residual[v][u] += flow;
            v = u;
        }
    }
    return maxFlow;
}

// -----------------------------
// 2. Push-Relabel (FIFO + Highest Label Variants)
// -----------------------------
class PushRelabel {
public:
    int n, source, sink;
    vector<vector<long long>> capacity, flow;
    vector<int> height, excess;
    vector<vector<int>> adj;
    vector<int> iter;  // current edge pointer for FIFO

    PushRelabel(int vertices, int s, int t)
        : n(vertices), source(s), sink(t), iter(vertices, 0) {
        capacity.assign(n, vector<long long>(n, 0));
        flow.assign(n, vector<long long>(n, 0));
        height.assign(n, 0);
        excess.assign(n, 0);
        adj.assign(n, vector<int>());
    }

    void addEdge(int u, int v, long long cap) {
        if (capacity[u][v] == 0) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        capacity[u][v] += cap;
    }

    void initializePreflow() {
        height[source] = n;
        excess[source] = 0;
        for (int v : adj[source]) {
            if (capacity[source][v] > 0) {
                flow[source][v] = capacity[source][v];
                flow[v][source] = -capacity[source][v];
                excess[v] += capacity[source][v];
                excess[source] -= capacity[source][v];
            }
        }
    }

    void push(int u, int v) {
        long long df = min((long long)excess[u], capacity[u][v] - flow[u][v]);
        flow[u][v] += df;
        flow[v][u] -= df;
        excess[u] -= df;
        excess[v] += df;
    }

    void relabel(int u) {
        int minHeight = INT_MAX;
        for (int v : adj[u]) {
            if (capacity[u][v] - flow[u][v] > 0) {
                minHeight = min(minHeight, height[v]);
            }
        }
        if (minHeight < INT_MAX) {
            height[u] = minHeight + 1;
        } else {
            height[u] = 2 * n;  // isolated node
        }
        iter[u] = 0;  // reset scanning
    }

    // -----------------------------
    // FIFO Push-Relabel (CORRECTED)
    // -----------------------------
    long long fifo() {
        initializePreflow();

        queue<int> q;
        vector<bool> inQueue(n, false);

        // Enqueue all nodes with excess
        for (int u = 0; u < n; ++u) {
            if (u != source && u != sink && excess[u] > 0) {
                q.push(u);
                inQueue[u] = true;
            }
        }

        auto discharge = [&](int u) {
            while (excess[u] > 0) {
                bool pushed = false;
                // Scan from current iterator position
                for (; iter[u] < adj[u].size(); ++iter[u]) {
                    int v = adj[u][iter[u]];
                    if (height[u] == height[v] + 1 &&
                        capacity[u][v] - flow[u][v] > 0) {
                        push(u, v);
                        pushed = true;

                        if (excess[v] > 0 && !inQueue[v] &&
                            v != source && v != sink) {
                            q.push(v);
                            inQueue[v] = true;
                        }
                        // Do NOT increment iter[u] — stay on this edge
                        break;
                    }
                }
                if (!pushed) {
                    relabel(u);
                }
            }
        };

        while (!q.empty()) {
            int u = q.front(); q.pop();
            inQueue[u] = false;

            if (excess[u] > 0 && u != source && u != sink) {
                discharge(u);
            }
        }
        return excess[sink];
    }

    // -----------------------------
    // Highest Label Push-Relabel
    // -----------------------------
    long long highestLabel() {
        initializePreflow();
        vector<int> count(2 * n, 0);
        vector<deque<int>> buckets(2 * n);

        for (int u = 0; u < n; ++u) {
            count[height[u]]++;
            buckets[height[u]].push_back(u);
        }

        int maxH = n - 1;
        while (maxH >= 0) {
            while (!buckets[maxH].empty()) {
                int u = buckets[maxH].front(); buckets[maxH].pop_front();
                if (u == source || u == sink || excess[u] <= 0) continue;

                bool pushed = false;
                for (int v : adj[u]) {
                    if (excess[u] > 0 && height[u] == height[v] + 1 && capacity[u][v] - flow[u][v] > 0) {
                        push(u, v);
                        if (excess[v] > 0 && v != source && v != sink) {
                            int h = height[v];
                            if (h < 2 * n && find(buckets[h].begin(), buckets[h].end(), v) == buckets[h].end()) {
                                buckets[h].push_back(v);
                                count[h]++;
                            }
                        }
                        pushed = true;
                    }
                }

                if (excess[u] > 0) {
                    relabel(u);
                    int newH = height[u];
                    if (newH < 2 * n) {
                        buckets[newH].push_back(u);
                        count[newH]++;
                        maxH = max(maxH, newH);
                    }
                }

                if (pushed && height[u] > maxH) {
                    maxH = height[u];
                }
            }
            while (maxH >= 0 && buckets[maxH].empty()) --maxH;
        }
        return excess[sink];
    }
};

// -----------------------------
// Random Graph Generator
// -----------------------------
FlowGraph generateRandomGraph(int n, double density, mt19937& rng) {
    FlowGraph g(n);
    uniform_real_distribution<double> prob(0.0, 1.0);
    uniform_int_distribution<int> capDist(1, 100);

    int source = 0, sink = n - 1;

    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            if (u != v && prob(rng) < density) {
                long long cap = capDist(rng);
                g.addEdge(u, v, cap);
            }
        }
    }

    // Ensure source and sink are connected
    if (g.capacity[source][sink] == 0 && source != sink) {
        g.addEdge(source, sink, capDist(rng));
    }

    return g;
}

// -----------------------------
// Timing Wrapper
// -----------------------------
template<typename Func>
double measureTime(Func&& func) {
    auto start = high_resolution_clock::now();
    func();
    auto end = high_resolution_clock::now();
    return duration_cast<duration<double>>(end - start).count();
}

// -----------------------------
// Main Experiment
// -----------------------------
int main() {
    const int NUM_RUNS = 20;
    const int MIN_N = 10, MAX_N = 750, N_STEP = 20;
    const int NUM_DENSITIES = 20;

    vector<int> nValues;
    for (int n = MIN_N; n <= MAX_N; n += N_STEP) {
        nValues.push_back(n);
    }

    vector<double> densities;
    for (int i = 0; i < NUM_DENSITIES; ++i) {
        double d = pow(10, -3.0 + i * (3.0 / (NUM_DENSITIES - 1)));
        densities.push_back(d);
    }

    ofstream ekOut("edmonds_karp_times.txt");
    ofstream fifoOut("fifo_push_relabel_times.txt");
    ofstream hlOut("highest_label_push_relabel_times.txt");

    ekOut << fixed << setprecision(6);
    fifoOut << fixed << setprecision(6);
    hlOut << fixed << setprecision(6);

    ekOut << "n";
    fifoOut << "n";
    hlOut << "n";
    for (double d : densities) {
        ekOut << "\t" << d;
        fifoOut << "\t" << d;
        hlOut << "\t" << d;
    }
    ekOut << "\n";
    fifoOut << "\n";
    hlOut << "\n";

    random_device rd;
    mt19937 rng(rd());

    cout << "Starting experiment...\n";
    cout << "n values: " << nValues.size() << ", density steps: " << NUM_DENSITIES << "\n";

    for (int ni = 0; ni < nValues.size(); ++ni) {
        int n = nValues[ni];
        int source = 0, sink = n - 1;

        ekOut << n;
        fifoOut << n;
        hlOut << n;

        cout << "Processing n = " << n << " (progress: " << (ni+1) << "/" << nValues.size() << ")\n";

        for (double density : densities) {
            double ekTime = 0.0, fifoTime = 0.0, hlTime = 0.0;

            for (int run = 0; run < NUM_RUNS; ++run) {
                FlowGraph g = generateRandomGraph(n, density, rng);

                // Edmonds-Karp
                auto ekGraph = g;
                ekTime += measureTime([&]() {
                    edmondsKarp(ekGraph, source, sink);
                });

                // FIFO Push-Relabel
                PushRelabel prFifo(n, source, sink);
                for (int u = 0; u < n; ++u) {
                    for (int v : g.adj[u]) {
                        prFifo.addEdge(u, v, g.capacity[u][v]);
                    }
                }
                fifoTime += measureTime([&]() {
                    prFifo.fifo();
                });

                // Highest Label Push-Relabel
                PushRelabel prHL(n, source, sink);
                for (int u = 0; u < n; ++u) {
                    for (int v : g.adj[u]) {
                        prHL.addEdge(u, v, g.capacity[u][v]);
                    }
                }
                hlTime += measureTime([&]() {
                    prHL.highestLabel();
                });
            }

            ekTime /= NUM_RUNS;
            fifoTime /= NUM_RUNS;
            hlTime /= NUM_RUNS;

            ekOut << "\t" << ekTime;
            fifoOut << "\t" << fifoTime;
            hlOut << "\t" << hlTime;
        }

        ekOut << "\n";
        fifoOut << "\n";
        hlOut << "\n";
    }

    ekOut.close();
    fifoOut.close();
    hlOut.close();

    cout << "Experiment completed. Output saved to:\n";
    cout << "  - edmonds_karp_times.txt\n";
    cout << "  - fifo_push_relabel_times.txt\n";
    cout << "  - highest_label_push_relabel_times.txt\n";

    return 0;
}

Test 1 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 4 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 5 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 6 (public)

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 7 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 8 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 9 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 10 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 11 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 12 (public)

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 13 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18 (public)

Group: 3

Verdict: TIME LIMIT EXCEEDED