Tobruk - explained

#include <bits/stdc++.h>
#define int long long

// Despre flux: https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33
/* Edmonds-Karp: https://www.youtube.com/watch?v=RppuJYwlcI8&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=38,
                 https://cp-algorithms.com/graph/edmonds_karp.html */
// Implementare personala la Edmonds-Karp: https://pastebin.com/1dDz6zL5
/* Dinic: https://www.youtube.com/watch?v=M6cm8UeeziI&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=42,
          https://cp-algorithms.com/graph/dinic.html */
// Implementare personala la Dinic: https://pastebin.com/4yXgZWyz
/* Optional, flux maxim de cost minim:
    * infoarena: https://www.infoarena.ro/problema/fmcm
    * cp-algorithms: https://cp-algorithms.com/graph/min_cost_flow.html
    * implementare personala:
        - SPFA: https: //www.infoarena.ro/problema/fmcm - mai ineficient
        - SPFA + Dijkstra: https://pastebin.com/ue5TRmLC - eficient
*/

using namespace std;

ifstream fin("tobruk.in");
ofstream fout("tobruk.out");

const int INF = 1e18L;

class FlowEdge { // structura unei muchii din graful rezidual pentru Dinic
    public:
        int u, v, capacity;

        FlowEdge(int u, int v, int capacity) {
            this -> u = u;
            this -> v = v;
            this -> capacity = capacity;
        }
};

class Dinic { // Flux maxim cu algoritmul lui Dinic, foarte eficient
    public:
        vector < FlowEdge > edges; // toate muchiile
        vector < vector < int > > adj; // lista de adiacenta a muchiilor
        int N, M = 0, source, sink; // numarul de noduri, de muchii, nodul sursa si cel destinatie
        vector < int > level, ptr; // nivelul fiecarui nod
        queue < int > Q; // coada pentru BFS

        Dinic(int N, int source, int sink) { // Inititalizare
            this -> N = N;
            this -> source = source;
            this -> sink = sink;
            adj.resize(N + 1);
            level.resize(N + 1);
            ptr.resize(N + 1);
        }

        void add_edge(int u, int v, int capacity) { // Adaugam muchiile in graful rezidual
            if(u == v)
                return; // muchiile de la nod la nod nu le punem
            edges.emplace_back(u, v, capacity); // adaugam muchia din input
            edges.emplace_back(v, u, 0); // adaugam muchia de cost 0 pentru graful rezidual
            adj[u].emplace_back(M++); // muchiile de cost 0 vor fi folosite pentru
            adj[v].emplace_back(M++); // "intoarcerea din decizii proaste"
        }

        bool BFS() { // BFS pentru a calcula nivelele
            while(!Q.empty()) {
                int curr = Q.front(); // nodul curent
                Q.pop();
                for(int id : adj[curr])
                    if(level[edges[id].v] == -1 && edges[id].capacity) { // daca capacitatea este 0,
                        level[edges[id].v] = level[curr] + 1; // muchia este saturata si trebuie ignorata
                        Q.emplace(edges[id].v); // daca se poate ajunge la nod il adaugam in coada
                    }
            }
            return level[sink] != -1; // daca nu putem ajunge la sink nu mai exista alte
            // drumuri de ameliorare si algoritmul trebuie oprit
        }

        int DFS(int u, int curr_flow) { // Cautam drumuri de ameliorare
            if(curr_flow == 0)
                return 0; // s-a ajuns la flux 0 deci nu mai are rost sa mai continuam
            if(u == sink)
                return curr_flow; // am ajuns la sink deci ne oprim
            for(int& p = ptr[u]; p < (int)adj[u].size(); ++p) { // nu consideram mereu toate muchhiile
                int id = adj[u][p],                             // deci mutam pointer-ul
                    v = edges[id].v;
                if(level[u] + 1 != level[v] || edges[id].capacity <= 0)
                    continue; // daca nu poti ajunge de la u la v sau muhcia u -> v este saturata ignoram
                int new_flow = DFS(v, min(curr_flow, edges[id].capacity));
                // noul flux este minimul dintre fluxul de pana acum(curr_flow) si fluxul obtinut ulterior
                if(new_flow == 0)
                    continue; // daca ajungem la flux nou 0 putem trece mai departe
                edges[id].capacity -= new_flow; // capacitatea muchiei u -> v scade cu noua cantitate de flux
                edges[id ^ 1].capacity += new_flow;
                // capacitatea muchiei reziduale v -> u creste cu noua cantitate de flux
                return new_flow; // returnam fluxul obtinut
            }
            return 0;
        }

        int max_flow() { // Fluxul maxim
            int flow_max = 0;
            while(true) {
                fill(level.begin(), level.end(), -1);
                level[source] = 0; // initializam nivelele
                Q.emplace(source); // pornim de la sursa
                if(!BFS())
                    break; // daca nu mai putem ajunge la sink salut
                fill(ptr.begin(), ptr.end(), 0); // initial toti pointerii sunt la 0(inceput, deci consideram toate muchiile)
                while(int curr_flow = DFS(source, INF))
                    flow_max += curr_flow; // pana mai gasim drumuri de ameliorare crestem fluxul maxim
            }
            return flow_max; // returnam rezultatul
        }
};

inline void min_self(int& a, int b) {
    a = min(a, b);
}

inline void max_self(int& a, int b) {
    a = max(a, b);
}

class squads {
    public:
        int position, strength, fuel, price;
};

class bases {
    public:
        int position, defense, oil;

        bool operator < (const bases& A) const { // comparator pentru sortare(crescator dupa puterea defensiva)
            return this -> defense < A.defense;
        }
};

int32_t main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int N, M;
    fin >> N >> M;
    vector < vector < int > > cost(N + 1, vector < int >(N + 1, INF));
    // cost[i][j] - lungimea drumului minim de la nodul i la nodul j
    for(int i = 1; i <= N; ++i)
        cost[i][i] = 0;
    while(M--) {
        int u, v;
        fin >> u >> v;
        cost[u][v] = cost[v][u] = min(cost[u][v], 1LL);
    }
    for(int i = 1; i <= N; ++i) // Folosim algoritmul lui Roy-Floyd pentru a calcula drumul minim dintre 2 noduri
        for(int j = 1; j <= N; ++j)
            for(int k = 1; k <= N; ++k)
                min_self(cost[i][j], cost[i][k] + cost[k][j]);
    int S, B, K;
    fin >> S >> B >> K;
    vector < squads > squad(S + 1);
    for(int i = 1; i <= S; ++i)
        fin >> squad[i].position >> squad[i].strength >> squad[i].fuel >> squad[i].price;
    vector < bases > base(B + 1);
    for(int i = 1; i <= B; ++i)
        fin >> base[i].position >> base[i].defense >> base[i].oil;
    sort(base.begin(), base.end()); // sortam bazele crescator dupa puterea defensiva
    vector < vector < pair < int , int > > > base_place(N + 1);
    for(int i = 1; i <= B; ++i) {
        int poz = base[i].position;
        if(base_place[poz].empty() || base_place[poz].back().second < base[i].oil)
            base_place[poz].emplace_back(base[i].defense, base[i].oil);
        /* Adaugam greedy la fiecare nod din graf bazele care sunt pozitionate in acesta si au puteri defensive cat mai
        mici si cantitati de petrol cat mai mari. Astfel daca am o baza cu putere defensiva mai mare si cantitate de
        petrol mai mica ca ultima aduagata, adaugarea acesteia este inutila, deci nu o facem. */
    }
    int source = 0, sink = S + 1; // sursa 0 si sink S + 1
    Dinic Graph(S + 2, source, sink); // initializam reteaua pentru flux
    int ans = 0;
    vector < int > val(S + 1);
    for(int i = 1; i <= S; ++i) { // iteram prin trupe
        bool found = false;
        for(int p = 1; p <= N; ++p) { // iteram prin nodurile grafului initial
            if(cost[squad[i].position][p] > squad[i].fuel)
                continue; // daca nu putem ajunge de la echipa la nod salut, mai departe
            auto it = upper_bound(base_place[p].begin(), base_place[p].end(), make_pair(squad[i].strength, INF));
            /* cautam binar(cu o functie ms STL) prima baza ce se afla in nodul p si are
               puterea defensiva <= puterea de asalt a trupei i */
            if(it != base_place[p].begin()) { // daca o si gasim
                --it;
                found = true; // marcam ca am gasit ceva pentru trupa i
                max_self(val[i], it -> second); // val[i] o setam la maximul valorilor de pana acum
            }
        }
        val[i] -= squad[i].price; // profitul e val[i] - price[i] - din enunt
        if(!found)
            val[i] = -INF; // daca nu gasim avem profit -INF
        if(val[i] >= 0) {
            ans += val[i]; // daca gasim muchie cu valoare pozitiva crestem rezultatul
            Graph.add_edge(source, i, val[i]); // adaugam muchia in retea
        }
        else
            Graph.add_edge(i, sink, -val[i]);
    }
    while(K--) {
        int u, v;
        fin >> u >> v; // citim dependentele
        Graph.add_edge(u, v, INF); // adaugam si dependentele in retea ca muchii de capacitate infinita
    }
    fout << ans - Graph.max_flow(); // rezultatul este ANS de pana acum - (costul taieturii minime, care e la fel cu fluxul maxim)
}