Cod sursa(job #2513611)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 23 decembrie 2019 15:21:29
Problema Algola Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <iostream>
#include <list>
#include <cstring>
#include <unordered_map>
#include <numeric>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long LL;
typedef long double LD;
const int inf = 2*(1e9);
const long long infl = 2*(1e18) + 10;
const long long MOD = 998244853;
const int NMAX = 55*95 + 10;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};

int C[NMAX][NMAX];
int F[NMAX][NMAX];
vector<int> G[NMAX];
int p[NMAX];
bool viz[NMAX];
int flow, minf;
int s, t;

queue<int> q;

bool bfs()
{
    q.push(s);
    memset(viz, 0, sizeof(viz));
    viz[s] = 1;

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

        if(u == t)
            continue;
        for(int i=0; i < G[u].size(); ++i)
        {
            int v = G[u][i];
            if(C[u][v] == F[u][v] || viz[v])
                continue;

            viz[v] = true;
            q.push(v);
            p[v] = u;
        }
    }
    return viz[t];
}

int n, m;
int pop[55];
pair<int, int> edges[305];
int c[305];

int getVertex(int u, int time){
    return n*time + u;
}

void addEdge(int u, int v, int cap){
    C[u][v] = cap;
    G[u].push_back(v);
    G[v].push_back(u);
}

void solve() {

    cin >> n >> m;


    flow = 0;

    s = 55 * 95;
    t = 55 * 95 + 1;

    int population = 0;

    for(int i = 1; i <= n; ++i){
        cin >> pop[i];
        population += pop[i];
    }

    for(int i = 1; i <= m; ++i){
        cin >> edges[i].first >> edges[i].second >> c[i];
    }

    int time = 0;
    // Add first edges

    // Add source to vertices where the population is located at time 0
    for(int i = 1; i <= n; ++i){
        addEdge(s, getVertex(i, 0), pop[i]);
    }
    addEdge(getVertex(1, 0), t, population);

    bfs();

    for (time = 0;; time++) {

        // Move along an edge (spend 1 unit of time)
        for(int i = 1; i <= m; ++i){
            addEdge(getVertex(edges[i].first, time), getVertex(edges[i].second, time+1), c[i]);
            addEdge(getVertex(edges[i].second, time), getVertex(edges[i].first, time+1), c[i]);
            int capi = c[i];

        }
        // Remain in the same vertex (no capacity limit)
        for(int i = 1; i <= n; ++i){
            addEdge(getVertex(i, time), getVertex(i, time + 1), population);
        }
        // Let the population to the sink at current time
        addEdge(getVertex(1, time), t, population);

        // Find augmenting paths
        while (bfs()) {
            for (int i = 0; i < G[t].size(); ++i) {
                int u = G[t][i];
                if (C[u][t] == F[u][t] || !viz[u])
                    continue;
                minf = 0xffffff;

                // Get minimum residual capacity on the path.
                p[t] = u;
                for (int i = t; i != s; i = p[i])
                    minf = min(minf, C[p[i]][i] - F[p[i]][i]);

                if (minf == 0)
                    continue;

                for (int i = t; i != s; i = p[i]) {
                    F[p[i]][i] += minf;
                    F[i][p[i]] -= minf;
                }
                // Increment
                flow += minf;
            }
        }

        if (flow == population) {
            cout << time << "\n";
            return;
        }
    }

}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << setprecision(16) << fixed;

    assert(freopen("algola.in", "rt", stdin));
    assert(freopen("algola.out", "wt", stdout));

    solve();

    return 0;
}