Cod sursa(job #3186754)

Utilizator Sumurduc_TeodoraSumurduc Teodora Sumurduc_Teodora Data 25 decembrie 2023 03:19:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
class graph{
private:
    vector<vector<int>> muchii;
    vector<vector<int>> rezidual;
    int n;
    vector<bool> vizitat;
    vector<int> tata;
    int s,t;
public:
    graph(int n):n(n){
        muchii.resize(2*n+3, vector<int>(2*n+3, 0));
        rezidual.resize(2*n+3, vector<int>(2*n+3, 0));
        vizitat.resize(2*n+3,false);
        tata.resize(2*n+3,-1);
        s=2*n+1;
        t=2*n+2;
    }
    bool bfs(){
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            ////cout<<u<<endl;
            vizitat[u]=true;
            q.pop();
            for (int v = 1; v < t+1; v++) {
                ///cout<<muchii[u][v]-rezidual[u][v]<<endl;
                if (!vizitat[v] && muchii[u][v]-rezidual[u][v] > 0) {
                    if(v==t)
                    {
                        tata[v] = u;
                        vizitat[v] = true;
                        return true;
                    }
                    q.push(v);
                    tata[v] = u;
                    vizitat[v] = true;
                    ///cout<<v<<endl;
                }
            }
        }
        return false;
    }
    void fordFulkerson()
    {
        int u, v;
        /*or (u = 0; u < t+1; u++)
            for (v = 0; v < t+1; v++)
                rezidual[u][v] = muchii[u][v];*/
        int max_flow = 0;
        while (bfs()) {
            int path_flow = INT_MAX;
            v=tata[t],u=t;
            ///cout<<"v "<<v<<endl;
            while(v!=-1) {
                path_flow = min(path_flow, muchii[v][u]-rezidual[v][u]);
                u=v;
                v=tata[u];
                ///cout<<"p "<<path_flow<<endl;
            }
            v=tata[t],u=t;
            while(v!=-1) {
                rezidual[u][v] -= path_flow;
                rezidual[v][u] += path_flow;
                ///cout<<"r "<<rezidual[u][v]<<" "<<rezidual[v][u]<<endl;
                u=v;
                v=tata[u];
                ///cout<<"r "<<rezidual[u][v]<<" "<<rezidual[v][u]<<endl;
            }
            max_flow += path_flow;

            for(int i=1;i<=2*n+2;i++)
            {

                //cout<<"ok"<<endl;
                vizitat[i]= false;
            }
        }
        g<<max_flow<<endl;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(rezidual[i][n+j]==1)
                {
                    g<<i<<" "<<j<<endl;
                }
            }
        }
    }
    void addMuchie(int a, int b, int i)
    {
        muchii[2*n+1][i]=a;
        muchii[n+i][2*n+2]=b;
        ///cout<<muchii[2*n+1][i]<<" "<<muchii[n+i][2*n+2]<<endl;
        for(int j=1;j<=n;j++)
            if(i!=j)
                muchii[i][n+j]=1;
    }
};

int main()
{
    int n,a,b;
    f>>n;
    graph graf(n);
    int s=2*n+1,t=2*n+2;
    for(int i=1;i<=n;i++)
    {
        f>>a>>b;
        graf.addMuchie(a,b,i);
    }
    graf.fordFulkerson();


    return 0;
}