Cod sursa(job #2469461)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 7 octombrie 2019 13:12:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define dim 300
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
queue <int> q;
vector <int> L[dim];
bitset <dim> fr;
int flux,j;
int C[dim][dim], F[dim][dim],i,p,u,minim,T[dim],n,x,y;
bool bfs()
{
    int nod,vecin;
    fr.reset();
    q.push(0);
    fr[0]=1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(i=0; i<L[nod].size(); i++)
        {

            vecin=L[nod][i];
            if(fr[vecin]==0 && C[nod][vecin]>F[nod][vecin])
            {

                q.push(vecin);

                T[vecin]=nod;

                fr[vecin]=1;

            }

        }

    }
    return fr[2*n+1];

}


int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>x>>y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
        C[0][i]=x;
        C[n+i][2*n+1]=y;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=n+1; j<=2*n; j++)
        {
            if(j-i==n)
                continue;
            L[i].push_back(j);
            L[j].push_back(i);
            C[i][j]=1;
        }
    }
    while (bfs())
    {
        for (int i=0; i<L[2*n+1].size(); i++)
        {

            p = L[2*n+1][i];

            if (C[p][2*n+1] > F[p][2*n+1] && fr[p] == 1)
            {

                minim = C[p][2*n+1] - F[p][2*n+1];

                u = p;
                while (u!= 0)
                {
                    minim =min(minim, C[ T[u] ][u] - F[ T[u] ][u]);
                    u = T[u];
                }
                flux += minim;

                F[p][2*n+1] += minim;

                F[2*n+1][p] -= minim;

                u = p;

                while (u != 0)
                {

                    F[ T[u] ][u] += minim;

                    F[ u ][ T[u] ] -= minim;

                    u = T[u];

                }

            }

        }

    }
    fout<<flux<<"\n";

    for (i=1; i<=n; i++)

        for (j=n+1; j<=2*n; j++)

            if (F[i][j] == 1)
            {

                fout<<i<<" "<<j-n<<"\n";

            }
}