Cod sursa(job #3187862)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 30 decembrie 2023 20:23:29
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 205;
const int INF = (1<<29);

class Graph{
private:
    int noduri;
    vector<vector<int>> adjList;
    vector<vector<int>> flux;
    vector<vector<int>> cap;
    vector<int> tata;
    vector<bool> ver;
public:
    Graph(int nr_noduri){
        this->noduri = nr_noduri;
        initGraph(nr_noduri+5);
    }

    void initGraph(int N){
        adjList.resize(N);
        flux.resize(N, vector<int>(N,0));
        cap.resize(N, vector<int>(N,0));
        tata.resize(N);
        ver.resize(N, false);
    }

    void pushBidirectional(int x,int y){
        adjList[x].push_back(y);
        adjList[y].push_back(x);
    }

    void setCapacity(int x,int y,int val){
        cap[x][y] = val;
    }

    int getFlux(int x,int y){
        return flux[x][y];
    }

    bool bfs(){
        for(int i=0;i<=this->noduri;i++)
            ver[i] = false;
        ver[0] = true;
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(int i=0;i<adjList[node].size();i++){
                int vecin = adjList[node][i];
                if(ver[vecin] == false and cap[node][vecin] > flux[node][vecin]){
                    ver[vecin] = true;
                    tata[vecin] = node;
                    q.push(vecin);
                }
            }
        }
        if(ver[this->noduri] == true) return true;
        return false;
    }

    int getGraphFlux(){
        int rasp = 0;

        while(bfs()){
            for(int i=0;i<adjList[this->noduri].size();i++){
                int node = adjList[this->noduri][i];
                if(ver[node] == true and cap[node][this->noduri] > flux[node][this->noduri]){
                    int minim = cap[node][this->noduri] - flux[node][this->noduri];
                    int naux = node;
                    while(naux!=0){
                        int t = tata[naux];
                        if(cap[t][naux] - flux[t][naux] < minim)
                            minim = cap[t][naux] - flux[t][naux];
                        naux = tata[naux];
                    }
                    if(minim == 0) continue;
                    rasp += minim;
                    flux[node][this->noduri] += minim;
                    flux[this->noduri][node] -= minim;

                    naux = node;
                    while(naux!=0){
                        int t = tata[naux];
                        flux[t][naux] += minim;
                        flux[naux][t] -= minim;
                        naux = tata[naux];
                    }
                }
            }
        }

        return rasp;
    }

};

int n,N,x,y;

int main(){
    fin >> n;
    N = 2*n+1;
    Graph g(N);
    for(int i=1;i<=n;i++){
        fin >> x >> y;
        g.pushBidirectional(0,i);
        g.setCapacity(0,i,x);

        g.pushBidirectional(n+i,N);
        g.setCapacity(n+i,N,y);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            g.pushBidirectional(i,n+j);
            g.setCapacity(i,n+j,1);
        }
    }

    int rasp = g.getGraphFlux();
    fout << rasp << '\n';

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g.getFlux(i,j+n) == 1){
                fout << i << ' ' << j << '\n';
            }
        }
    }

    return 0;
}