Cod sursa(job #3193339)

Utilizator raluca_rRadu Raluca raluca_r Data 14 ianuarie 2024 14:42:35
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int N,M,k,x,parinte[202],dist,cap[202][202],flux[202][202],in,out;
bool viz[202];

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

void bfs()
{
    for(int i=1; i<=2*N+1 ;i++)
    {
        parinte[i]=-1;
        viz[i]=false;
    }
    queue <int> q;
    q.push(0);
    viz[0]=true;
    parinte[0]=-1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(x != dist)
        {
            if(x >= 1 && x <= N)
            {
                for(int i=N+1; i<=2*N; i++)
                    if(!viz[i] && cap[x][i] != flux[x][i])
                    {
                        viz[i]=true;
                        parinte[i]=x;
                        q.push(i);
                    }
            }
            else
            {
                for(int i=1;i<=N;i++)
                    if(!viz[i] && cap[x][i] != flux[x][i])
                    {
                        viz[i]=true;
                        parinte[i]=x;
                        q.push(i);
                    }
                if(x != 0 && !viz[dist] && cap[x][dist] != flux[x][dist])
                {
                    viz[dist]=true;
                    parinte[dist]=x;
                    q.push(dist);
                }
            }
        }
    }
}
int maxim()
{
    int flux_max=0;
    bfs();
    while(viz[dist])
    {
        for(int i=N+1;i<=2*N;i++)
        {
            if(viz[i] && cap[i][dist] != flux[i][dist])
            {
                parinte[dist]=i;
                int flux_min=100000,poz=dist;
                while(poz)
                {
                    flux_min=min(flux_min, cap[parinte[poz]][poz] - flux[parinte[poz]][poz]);
                    poz=parinte[poz];
                }
                if(flux_min != 0)
                {
                    flux_max+=flux_min;
                    poz=dist;
                    while(poz)
                    {
                        flux[parinte[poz]][poz]+=flux_min;
                        flux[poz][parinte[poz]]-=flux_min;
                        poz=parinte[poz];
                    }
                }
            }
        }
        bfs();
    }
    return flux_max;
}
int main()
{
    fin >> N;
    dist= 2 * N + 1;
    for(int i=1;i<=N;i++)
    {
        fin >> out >> in;
        M+=out;
        cap[0][i]=out;
        cap[i+N][dist]=in;
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(j!=i)
                cap[i][j+N]=1;
    fout << maxim() << '\n';
    for(int i=1;i<=N;i++)
        for(int j=N+1;j<=2*N;j++)
            if(flux[i][j])
                fout << i << ' ' << j << '\n';
    fin.close();
    fout.close();
    return 0;
}