Cod sursa(job #3190898)

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

using namespace std;

template<typename T, typename U>
class Graph {
private:
    unordered_map<T, vector<U>> 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){
        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; }

    // 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);
};

template<typename T, typename U> int Graph<T, U>::BFS(int start, int finish){
    fill(this->parent.begin(), this->parent.end(), -1);
    this->parent[start] = -2;
    queue<pair<int, int>> q;
    q.push({start, INT_MAX});
    while(!q.empty()){
        int curr = q.front().first;
        int flow = q.front().second;
        q.pop();
        for(int next : this->adjList[curr]){
            if(this->parent[next] == -1 && this->capacity[curr][next] > this->flow[curr][next]){
                this->parent[next] = curr;
                int newFlow = min(flow, this->capacity[curr][next] - this->flow[curr][next]);
                if(next == finish){
                    return newFlow;
                }
                q.push({next, newFlow});
            }
        }
    }
    return 0;
}

template<typename T, typename U> int Graph<T, U>::maxFlow(int start, int finish){
    int flow = 0;
    while(true){
        int newFlow = BFS(start, finish);
        if(newFlow == 0){
            break;
        }
        flow += newFlow;
        int curr = finish;
        while(curr != start){
            int prev = this->parent[curr];
            this->flow[prev][curr] += newFlow;
            this->flow[curr][prev] -= newFlow;
            curr = prev;
        }
    }
    return flow;
}

template<typename T, typename U> void Graph<T, U>::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 {
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<int, int> 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<int, int> 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<int, int> 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<int, int> 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<int, int> 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<int, int> 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/
    void ReconstructItinerary(){

    }

    // https://leetcode.com/problems/valid-arrangement-of-pairs/
    void ValidArrangementOfPairs(){

    }

    // https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/
    void ShortestPathVisitingAllNodes(){

    }

};

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