Cod sursa(job #3190600)

Utilizator sumithesumSumurduc Alexandru sumithesum Data 7 ianuarie 2024 19:04:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>

using namespace std;

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

class graph{
private:
    vector<vector<int>> cap;
    vector<vector<int>> flux;
    vector<bool> vizitat;
    vector<int> tati;
    int n,start,end,size;
public:
    graph(int n):n(n){
        size = 2 * n + 3;
        start = 2*n+1;
        end = 2*n+2;
        init();
        citire();
    }
    void init(){
        cap.resize(size, vector<int>(size, 0));
        flux.resize(size, vector<int>(size, 0));
        vizitat.resize(size,false);
        tati.resize(size,-1);
    }
    void citire(){
        int x,y;
        for(int i=1;i<=n;i++) {
            fin >> x >> y;
            addMuchie(x, y, i);
        }
    }
    bool bfs(){
        for(int i=1;i<=2*n+2;i++)
            vizitat[i]= false;

        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int u = q.front();

            vizitat[u]=true;
            q.pop();
            for (int v = 1; v < end+1; v++) {

                if (!vizitat[v] && cap[u][v]-flux[u][v] > 0) {

                    q.push(v);
                    tati[v] = u;
                    vizitat[v] = true;
                    if(v == end)
                        return true;

                }
            }
        }
        return false;
    }
    int fordFulkerson()
    {

        int raspuns = 0;
        while (bfs()) {
            int current, next;
            int minim = INT_MAX;
            next=tati[end],current=end;

            while(next!=-1) {
                minim = min(minim, cap[next][current]-flux[next][current]);
                current=next;
                next=tati[current];

            }
            next=tati[end],current=end;
            while(next!=-1) {
                flux[current][next] -= minim;
                flux[next][current] += minim;

                current=next;
                next=tati[current];

            }
            raspuns += minim;


        }
        return raspuns;
    }
    void addMuchie(int a, int b, int i)
    {
        cap[start][i]=a;
        cap[n+i][end]=b;

        for(int j=1;j<=n;j++)
            if(i!=j)
                cap[i][n+j]=1;
    }
    void   afisare(){
        fout << fordFulkerson() <<endl;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(flux[i][n+j]==1)
                    fout<<i<<" "<<j<<endl;



    }
};

int main()
{
    int n,a,b;
    fin >> n;
    graph graf(n);

    graf.afisare();


    return 0;
}