Cod sursa(job #2691261)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 27 decembrie 2020 18:32:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

int n,cap[205][205],flux[205][205],tata[205],nr;
bool fost[205];
vector<int>vecini[205];
queue<int>coada;

bool pompeaza()
{
    for(int i=0; i<=n+n+1; i++) fost[i]=0;
    coada.push(0);
    fost[0]=1;

    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();

        if(nod==2*n+1) continue;

        for(int i=0; i<vecini[nod].size(); i++)
        {
            int x=vecini[nod][i];

            if(fost[x]||cap[nod][x]==flux[nod][x]) continue;

            coada.push(x);
            fost[x]=1;
            tata[x]=nod;
        }
    }
    return fost[2*n+1];
}

int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        int a,b;
        f>>a>>b;
        nr+=a;
        cap[0][i]=a;
        vecini[i].push_back(0);
        vecini[0].push_back(i);
        for(int j=1; j<=n; j++)
            if(i!=j) vecini[i].push_back(j+n),vecini[j+n].push_back(i),cap[i][j+n]=1;
        cap[i+n][2*n+1]=b;
        vecini[i+n].push_back(2*n+1);
        vecini[2*n+1].push_back(i+n);
    }
    g<<nr<<'\n';

    while( pompeaza() )
    {
        for(int i=0; i<vecini[2*n+1].size(); i++)
        {
            int x=vecini[2*n+1][i];
            if( !fost[x]&&cap[2*n+1][x]==flux[2*n+1][x] ) continue;
            tata[2*n+1]=x;
            int cup=100005;
            for(int j=2*n+1; j!=0; j=tata[j]) cup=min(cup,cap[tata[j]][j]-flux[tata[j]][j]);
            if(cup==0) continue;
            for(int j=2*n+1; j!=0; j=tata[j]){
              flux[tata[j]][j]+=cup;
              flux[j][tata[j]]-=cup;
            }
        }
    }
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
     if(flux[i][j+n]!=0) g<<i<<' '<<j<<'\n';
}