Cod sursa(job #2385065)

Utilizator alexge50alexX AleX alexge50 Data 21 martie 2019 16:19:15
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.04 kb
/*
 * A computer is like air conditioning - it becomes useless when you
 * open Windows.
 *      - Linus Torvalds
 */

#include <fstream>
#include <vector>
#include <memory>
#include <queue>
#include <iostream>

#pragma GCC optimize ("-O3,-ffast-math")
#pragma GCC target("sse3")

#define o3 __attribute__((optimize("-O3")))
#define always_inline __inline__ __attribute__((always_inline))

#define fast_shit o3 always_inline


const int MAX_N = 1000;

struct Network
{
    std::vector<int> neighbours[MAX_N];
    long long costs[MAX_N][MAX_N]{};
    int nNodes = 0;
};

struct State
{
    bool was[MAX_N];
    int last[MAX_N];
    long long flux[MAX_N][MAX_N];
};

fast_shit bool bfs(int source, int destination);
fast_shit long long flux_value(int x, int source);
fast_shit void flux_update(long long value, int x, int source);

static Network network;
static State state;

int main()
{
    std::ifstream fin("maxflow.in");
    std::ofstream fout("maxflow.out");


    int source, destination;

    fin >> network.nNodes;
    int m;

    fin >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;

        network.neighbours[a - 1].push_back(b - 1);
        network.costs[a - 1][b - 1] = c;

        network.neighbours[b - 1].push_back(a - 1);
    }

    source = 0;
    destination = network.nNodes - 1;

    int flux = 0;
    while(bfs(source, destination))
    {
        for(auto i: network.neighbours[destination])
        {
            if(state.was[i] && state.flux[i][destination] != network.neighbours[i][destination])
            {
                state.last[destination] = i;
                auto x = flux_value(destination, source);

                flux += x;
                flux_update(x, destination, source);
            }
        }
    }

    fout << flux;

    return 0;
}

fast_shit long long flux_value(int x, int source)
{
    long long val = network.costs[state.last[x]][x] - state.flux[state.last[x]][x];
    int y;

    while(x != source)
    {
        y = state.last[x];
        val = std::min(val, network.costs[y][x] - state.flux[y][x]);
        x = y;
    }

    return val;
}

fast_shit void flux_update(long long value, int x, int source)
{
    int y;

    while(x != source)
    {
        y = state.last[x];
        state.flux[y][x] += value;
        state.flux[x][y] -= value;
        x = y;
    }
}

fast_shit bool bfs(int source, int destination)
{
    static std::queue<int> q;

    for(int i = 0; i < network.nNodes; i++)
    {
        state.was[i] = false;
        state.last[i] = -1;
    }

    q.push(source);
    state.was[source] = true;

    while(!q.empty())
    {
        int x = q.front();
        q.pop();

        if(x == destination)
        {
            while(!q.empty()) q.pop();
            return true;
        }

        for(auto y: network.neighbours[x])
        {
            if(!state.was[y] && state.flux[x][y] < network.costs[x][y])
            {
                state.last[y] = x;
                state.was[y] = true;
                q.push(y);
            }
        }
    }

    return state.was[destination];
}