Cod sursa(job #2668161)

Utilizator stefantagaTaga Stefan stefantaga Data 4 noiembrie 2020 16:21:13
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> v[305];
int n,tata[205],c[205][205],flux[205][205],lim,i,x,y,j,nod,sol,solutie;
bool exista_drum(int inceput)
{
    queue <int> q;
    int i;
    for (i=0;i<=lim;i++)
    {
        tata[i]=-1;
    }
    tata[inceput]=0;
    q.push(inceput);
    while (!q.empty())
    {
        int curent=q.front();
        q.pop();
        for (int j=0;j<v[curent].size();j++)
        {
            int nod=v[curent][j];
            if (tata[nod]==-1&&c[curent][nod]>flux[curent][nod])
            {
                tata[nod]=curent;
                q.push(nod);
                if (nod==lim)
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    f>>n;
    lim=2*n+1;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        v[0].push_back(i);
        v[i].push_back(0);
        c[0][i]=x;
        v[n+i].push_back(lim);
        v[lim].push_back(n+i);
        c[n+i][lim]=y;
    }
    for (i=1;i<=n;i++)
    {
        for (j=n+1;j<=lim-1;j++)
        {
            if (j-i!=n)
            {
                v[i].push_back(j);
                v[j].push_back(i);
                c[i][j]=1;
            }
        }
    }
    while (exista_drum(0)==1)
    {
        for (j=0;j<v[lim].size();j++)
        {
            nod=v[lim][j];
            if (tata[nod]==-1)
            {
                continue;
            }
            sol=c[nod][lim]-flux[nod][lim];
            while (nod!=0)
            {
                sol=min(sol,c[tata[nod]][nod]-flux[tata[nod]][nod]);
                nod=tata[nod];
            }
            solutie+=sol;
            nod=v[lim][j];
            flux[nod][lim]+=sol;
            flux[lim][nod]-=sol;
            while (nod!=0)
            {
                flux[tata[nod]][nod]+=sol;
                flux[nod][tata[nod]]-=sol;
                nod=tata[nod];
            }
        }
    }
    g<<solutie<<'\n';
    for (i=1;i<=n;i++)
    {
        for (j=n+1;j<=lim-1;j++)
        {
            if (j-i!=n&&flux[i][j]==1)
            {
                g<<i<<" "<<j-n<<'\n';
            }
        }
    }
    return 0;
}