Cod sursa(job #3190744)

Utilizator AndreiKatsukiAndrei Dogarel AndreiKatsuki Data 7 ianuarie 2024 21:25:23
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <bits/stdc++.h>

using namespace std;


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

    int BFS(int start, int finish);

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

    // Getters & Setters
    vector<vector<int>> getFlow(){ return this->flow; }
    vector<vector<int>> getCapacity(){ return this->capacity; }

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

    int maxFlow(int start, int finish);
};

int Graph::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;
}

int Graph::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;
}


class Solution {
public:
    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";
                }
            }
        }
    }
};

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