Cod sursa(job #3191000)

Utilizator AndreiKatsukiAndrei Dogarel AndreiKatsuki Data 8 ianuarie 2024 16:17:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 14.93 kb
#include <bits/stdc++.h>

using namespace std;


class Graph {
private:
    vector<vector<int>> adjList;
    vector<vector<int>> capacity, flow;
    vector<int> parent;
    vector<vector<bool>> hasEdge;
    vector<bool> visited;

    int BFS(int start, int finish);     // Functie BFS ajutatoare pentru algoritmul de flux maxim 

public:
    // Constructori
    Graph(int size){
        adjList.resize(size + 5);
        capacity.resize(size + 5, vector<int>(size + 5, 0));
        flow.resize(size + 5, vector<int>(size + 5, 0));
        parent.resize(size + 5);
        hasEdge.resize(size + 5, vector<bool>(size + 5, false));
        visited.resize(size + 5, false);
    }

    // Getters & Setters
    vector<vector<int>> getFlow() const { return this->flow; }
    vector<vector<int>> getCapacity() const { return this->capacity; }
    void setFlow(int x, int y, int value){ this->flow[x][y] += value; }
    void setCapacity(int x, int y, int value){ this->capacity[x][y] += value; }

    // Operatori
    vector<int>& operator [] (int index){
        try{
            if(index > this->adjList.size() || index < 0){
                throw runtime_error("Index invalid!");
            }
            return this->adjList[index];
        }
        catch(const exception& e){
            cout << e.what() << "\n";
        }
    }

    // Metode
    bool verifyEdge(int x, int y) const { return this->hasEdge[x][y]; }

    bool verifyIfVisited(int node) const { return this-> visited[node]; }

    void add(int x, int y, int capacity){
        this->adjList[x].push_back(y);
        this->adjList[y].push_back(x);
        this->capacity[x][y] = capacity;
        this->hasEdge[x][y] = true;
        this->hasEdge[y][x] = true;
    }

    int maxFlow(int start, int finish);

    void findMinimumVertexCover(int node);
};

int Graph::BFS(int start, int finish){
    fill(this->visited.begin(), this->visited.end(), false);
    queue<int> q;
    this->visited[start] = 1;
    q.push(start);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node == finish){
            break;
        }
        for(auto it : this->adjList[node]){
            if(!this->visited[it] && this->capacity[node][it] > this->flow[node][it]){
                this->visited[it] = 1;
                parent[it] = node;
                q.push(it);
            }
        }
    }
    return this->visited[finish];
}

int Graph::maxFlow(int start, int finish){
    int flow = 0;
    while(BFS(start, finish)){
        for(int it : this->adjList[finish]){
            if(this->visited[it] && capacity[it][finish] != this->flow[it][finish]){
                int node = finish, currFlux = INT_MAX;
                parent[finish] = it;
                while(node != start){
                    int prev = parent[node];
                    currFlux = min(currFlux, this->capacity[prev][node] - this->flow[prev][node]);
                    node = prev;
                }
                if(currFlux == 0){
                    continue;
                }
                node = finish;
                while(node != start){
                    int prev = parent[node];
                    this->flow[prev][node] += currFlux;
                    this->flow[node][prev] -= currFlux;
                    node = prev;
                }
                flow += currFlux;
            }
        }
    }
    return flow;
}

void Graph::findMinimumVertexCover(int node){
    this->visited[node] = true;
    for(int next : this->adjList[node]){
        if(!this->visited[next] && this->capacity[node][next] > this->flow[node][next]){
            findMinimumVertexCover(next);
        }
    }
}


class Solution {
private:
    void findItineraryHelper(string start, vector<string>& sol, unordered_map<string, vector<string>>& Graph){
        while(!Graph[start].empty()){
            string next = Graph[start].back();
            Graph[start].pop_back();
            findItineraryHelper(next, sol, Graph);
        }
        sol.push_back(start);
    }

    void validArrangementHelper(int start, vector<vector<int>>& sol, unordered_map<int, vector<int>>& Graph){
        while(!Graph[start].empty()){
            int next = Graph[start].back();
            Graph[start].pop_back();
            validArrangementHelper(next, sol, Graph);
            sol.push_back({start, next});
        }
    }

public:
    // https://www.infoarena.ro/problema/harta
    void Harta(){
        ifstream fin("harta.in");
        ofstream fout("harta.out");

        int n, nrMuchii = 0;
        fin >> n;
        int s = 0, t = 2 * n + 1;
        Graph Graf(t);
        for(int i = 1; i <= n; ++i){
            int x, y;
            fin >> x >> y;
            nrMuchii += x;
            for(int j = 1; j <= n; ++j){
                if(j != i){
                    Graf.add(i, j + n, 1);
                }
            }
            Graf.add(s, i, x);
            Graf.add(i + n, t, y);
        }
        Graf.maxFlow(s, t);
        fout << nrMuchii << "\n";
        for(int i = 1; i <= n; ++i){
            for(int j = n + 1; j < t; ++j){
                if(Graf.getFlow()[i][j]){
                    fout << i << " " << j - n << "\n";
                }
            }
        }
    }

    // https://codeforces.com/problemset/problem/546/E
    void SoldierAndTraveling(){
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int n, m, sumaA = 0, sumaB = 0;
        cin >> n >> m;
        int s = 0, t = 2 * n + 1;
        Graph Graf(t);
        for(int i = 1; i <= n; ++i){
            int x;
            cin >> x;
            Graf.add(s, i, x);
            sumaA += x;
        }
        for(int i = 1; i <= n; ++i){
            int x;
            cin >> x;
            Graf.add(i + n, t, x);
            sumaB += x;
        }
        for(int i = 1; i <= m; ++i){
            int x, y;
            cin >> x >> y;
            Graf.add(x, y + n, INT_MAX);
            Graf.add(y, x + n, INT_MAX);
        }
        for(int i = 1; i <= n; ++i){
            Graf.add(i, i + n, INT_MAX);
        }
        int res = Graf.maxFlow(s, t);
        if(res == sumaA && sumaA == sumaB){
            cout << "YES\n";
            for(int i = 1; i <= n; ++i){
                for(int j = n + 1; j <= 2 * n; ++j){
                    cout << Graf.getFlow()[i][j] << " ";
                }
                cout << "\n";
            } 
        }
        else{
            cout << "NO";
        }
    }

    // https://infoarena.ro/problema/ghizi
    void Ghizi(){
        ifstream fin("ghizi.in");
        ofstream fout("ghizi.out");

        int n, k, s = 101, t = 100;
        vector<pair<int, int>> vol;
        fin >> n >> k;
        Graph Graf(s);
        for(int i = 1; i <= n; ++i){
            int x, y;
            fin >> x >> y;
            vol.push_back({x, y});
            if(!Graf.verifyEdge(x, y)){
                Graf.add(x, y, 1);
            }
            else{
                Graf.setCapacity(x, y, 1);
            }
        }
        Graf.add(s, 0, k);
        Graf.maxFlow(s, t);
        vector<int> res;
        for(int i = 0; i < vol.size(); ++i){
            if(Graf.getFlow()[vol[i].first][vol[i].second]){
                res.push_back(i + 1);
                Graf.setFlow(vol[i].first, vol[i].second, -1);
            }
        }
        fout << res.size() << "\n";
        for(auto it : res){
            fout << it << " ";
        }
    }

    // https://www.infoarena.ro/problema/senat
    void Senat(){
        ifstream fin("senat.in");
        ofstream fout("senat.out");

        int n, m;
        fin >> n;
        fin >> m;
        fin.get();
        char a[10000];
        int s = 0, t = n + m + 1;
        Graph Graf(t);
        for(int i = 1; i <= m; ++i){
            fin.getline(a, 10000);
            int nr = 0, size = strlen(a);
            for(int j = 0; j < size; ++j){
                if(isdigit(a[j])){
                    nr = nr * 10 + (a[j] - '0');
                }
                else if(a[j] == ' ' && j < size - 1){
                    Graf.add(nr, i + n, 1);
                    nr = 0;
                }
            }
            Graf.add(nr, i + n, 1);
            Graf.add(i + n, t, 1);
        }
        for(int i = 1; i <= n; ++i){
            Graf.add(s, i, 1);
        }
        int total = Graf.maxFlow(s, t);
        if(total == m){
            for(int i = 1; i <= m; ++i){
                for(int j = 1; j <= n; ++j){
                    if(Graf.getFlow()[j][i + n] == 1){
                        fout << j << "\n";
                        break;
                    }
                }
            }
        }
        else{
            fout << 0;
        }
    }

    // https://www.infoarena.ro/problema/paznici
    void Paznici(){
        ifstream fin("paznici.in");
        ofstream fout("paznici.out");

        int n, m;
        fin >> n >> m;
        int s = 0, t = n + m + 1;
        Graph Graf(t);
        for(int i = 1; i <= n; ++i){
            string a;
            fin >> a;
            for(int j = 0; j < a.size(); ++j){
                if(a[j] == '1'){
                    Graf.add(i, j + n + 1, 1);
                }
            }
            Graf.add(s, i, 1);
        }
        for(int i = 1; i <= m; ++i){
            Graf.add(i + n, t, 1);
        }
        Graf.maxFlow(s, t);
        Graf.findMinimumVertexCover(0);
        string res = "";
        for(int i = 1; i <= n; ++i){
            if(!Graf.verifyIfVisited(i)){
                res += ('A' + i - 1);
            }
        }
        for(int i = 1; i <= m; ++i){
            if(Graf.verifyIfVisited(i + n)){
                res += ('a' + i - 1);
            }
        }
        fout << res;
    }

    // https://csacademy.com/contest/archive/task/no-prime-sum/
    void NoPrimeSum(){
        int n;
        vector<int> numbers, leftNodes, rightNodes;
        vector<bool> primes(200005, true);
        cin >> n;
        for(int i = 1; i <= n; ++i){
            int x;
            cin >> x;
            numbers.push_back(x);
        }
        for(int i : numbers){
            if(i % 2 == 0){
                leftNodes.push_back(i);
            }
            else{
                rightNodes.push_back(i);
            }
        }
        primes[0] = primes[1] = false;
        for(int i = 2; i <= 200005 / 2; ++i){
            if(primes[i]){
                for(int j = 2; j * i <= 200005; ++j){
                    primes[i * j] = false;
                }
            }
        }
        int s = 0, t = leftNodes.size() + rightNodes.size() + 1;
        Graph Graf(t);
        for(int i = 0; i < leftNodes.size(); ++i){
            for(int j = 0; j < rightNodes.size(); ++j){
                if(primes[leftNodes[i] + rightNodes[j]]){
                    int u = i + 1, v = j + 1 + leftNodes.size();
                    Graf.add(u, v, 1);
                }
            }
        }
        for(int i = 1; i <= leftNodes.size(); ++i){
            Graf.add(s, i, 1);
        }
        for(int i = 1; i <= rightNodes.size(); ++i){
            Graf.add(i + leftNodes.size(), t, 1);
        }
        Graf.maxFlow(s, t);
        vector<int> sol;
        Graf.findMinimumVertexCover(s);
        for(int i = 0; i < leftNodes.size(); ++i){
            if(!Graf.verifyIfVisited(i + 1)){
                sol.push_back(leftNodes[i]);
            }
        }
        for(int i = 0; i < rightNodes.size(); ++i){
            if(Graf.verifyIfVisited(i + leftNodes.size() + 1)){
                sol.push_back(rightNodes[i]);
            }
        }
        cout << sol.size() << "\n";
        for(auto it : sol){
            cout << it << " ";
        }
    }

    // https://leetcode.com/problems/reconstruct-itinerary/description/
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> Graph;
        for(auto ticket : tickets){
            Graph[ticket[0]].push_back(ticket[1]);
        }
        for(auto& [airport, dest] : Graph){
            sort(dest.rbegin(), dest.rend());
        }
        vector<string> sol;
        findItineraryHelper("JFK", sol, Graph);
        reverse(sol.begin(), sol.end());
        return sol;
    }

    // https://leetcode.com/problems/valid-arrangement-of-pairs/
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        int n = pairs.size();
        unordered_map<int, vector<int>> Graph;
        unordered_map<int, int> inDeg, outDeg;
        for(auto pair : pairs){
            inDeg[pair[1]]++;
            outDeg[pair[0]]++;
            Graph[pair[0]].push_back(pair[1]);
        }
        int start = -1;
        for(auto pair : Graph){
            int i = pair.first;
            if(outDeg[i] == inDeg[i] + 1){
                start = i;
            }
        }
        if(start == -1){
            start = (*Graph.begin()).first;
        }
        vector<vector<int>> sol;
        validArrangementHelper(start, sol, Graph);
        reverse(sol.begin(), sol.end());
        return sol;
    }

    // https://leetcode.com/problems/shortest-path-visiting-all-nodes/
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int allVisitedConfig = (1 << n) - 1;
        vector<vector<bool>> vis(allVisitedConfig + 1, vector<bool>(n + 1, false));
        queue<pair<int, pair<int, int>>> q; // {currConfig, {node, dist}}
        for(int i = 0; i < n; ++i){
            q.push({(1 << i), {i, 0}});
            vis[1 << i][i] = true;
        }
        while(!q.empty()){
            int currConfig = q.front().first;
            int node = q.front().second.first;
            int dist = q.front().second.second;
            q.pop();
            if(currConfig == allVisitedConfig){
                return dist;
            }
            for(auto neigh : graph[node]){
                int newConfig = currConfig | (1 << neigh);
                if(!vis[newConfig][neigh]){
                    q.push({newConfig, {neigh, dist + 1}});
                    vis[newConfig][neigh] = true;
                }
            }
        }
        return -1;
    }

    // https://infoarena.ro/problema/negot
    void Negot(){
        ifstream fin("negot.in");
        ofstream fout("negot.out"); 

        int n, m, k;
        fin >> n >> m >> k;
        int s = 0, t = m + n + 1;
        Graph Graf(t);
        for(int i = 1; i <= n; ++i){
            int x;
            fin >> x;
            for(int j = 1; j <= x; ++j){
                int y;
                fin >> y;
                Graf.add(i, n + y, 1);
            }
            Graf.add(s, i, k);
        }
        for(int i = 1; i <= m; ++i){;
            Graf.add(n + i, t, 1);
        }
        fout << Graf.maxFlow(s, t);
    }
};

int main(){
    Solution s;
    s.Harta();
    return 0;
}