Cod sursa(job #2663571)

Utilizator teisanumihai84Mihai Teisanu teisanumihai84 Data 26 octombrie 2020 20:06:05
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <vector>
#include <deque>
#define INF 100000000
#define DIM 210
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, m, c[DIM][DIM], flux[DIM][DIM], f[DIM], t[DIM], i, j, sol, in, ex;
deque <int> q;
vector <int> L[DIM];
/// flux e la inceput 0
int bfs()
{
    int dim=2*n+1;
    int ok=0;
    f[0]=1;
    for (i=1; i<=dim; i++)
        f[i]=0;
    q.clear();
    q.push_back(0);
    while (!q.empty())
    {
        int nod=q.front();
        if (nod==dim)
            ok=1;
        for (i=0; i<L[nod].size(); i++)
        {
            int vecin=L[nod][i];
            if (!f[vecin] && c[nod][vecin]>flux[nod][vecin])
            {
                q.push_back(vecin);
                f[vecin]=1;
                t[vecin]=nod;
            }
        }
        q.pop_front();
    }
    return ok;
}
int main ()
{
    fin>>n;
    int dim=2*n+1;
    for (i=1; i<=n; i++)
    {
        fin>>ex>>in;
        sol+=ex;
        L[0].push_back(i); L[i].push_back(0);
        c[0][i]=ex; c[i][0]=0;
        for (j=1; j<=n; j++)
        {
            if (j!=i)
            {
                L[i].push_back(n+j); L[n+j].push_back(i); c[i][n+j]=1;
            }
        }
        L[n+i].push_back(dim); L[dim].push_back(n+i);
        c[n+i][dim]=in;
    }
    while (bfs())
    {
        int minim=INF; i=dim; t[0]=-1;
        while (t[i]!=-1)
        {
            minim=min(minim, c[t[i]][i]-flux[t[i]][i]);
            i=t[i];
        }
        i=dim;
        while (t[i]!=-1)
        {
            flux[t[i]][i]+=minim;
            flux[i][t[i]]-=minim;
            i=t[i];
        }
    }
    fout<<sol<<"\n";
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (flux[i][n+j]==1)
                fout<<i<<" "<<j<<"\n";
}