Cod sursa(job #2660789)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 20 octombrie 2020 15:43:26
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda trainingflow Marime 2.2 kb
#include <fstream>
#include <bitset>
#include <vector>
#define DIM 210
#define INF 1000000000
using namespace std;

ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n,i,j,x,y,frunza,dif,flux;
vector <int> L[DIM];
int Q[DIM],c[DIM][DIM],f[DIM][DIM],t[DIM];
bitset <DIM> v;
int bfs() {
    int p,u;
    v.reset();
    p = u = 1;
    Q[1] = 0;
    v[0] = 1;
    int dest = 0;
    while (p <= u){
        for (int i=0;i<L[ Q[p] ].size();i++){
            int vecin = L[ Q[p] ][i];
            if (v[vecin] == 0 && c[ Q[p] ][vecin] > f[ Q[p] ][vecin]) {
                u++;
                Q[u] = vecin;
                v[vecin] = 1;
                t[vecin] = Q[p];
                if (vecin == 2*n+1)
                    dest = 1;
            }
        }

        p++;
    }
    return dest;
}

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;
    }
    /// punem muchie intre fiecare cu fiecare
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i != j){
                L[i].push_back (n+j);
                L[n+j].push_back (i);
                c[i][n+j] = 1;
            }

    while (bfs()) {
        for (int i=0; i<L[2*n+1].size(); i++) {
            frunza = L[2*n+1][i];
            if (c[frunza][2*n+1] <= f[frunza][2*n+1])
                continue;


            dif = c[frunza][2*n+1] - f[frunza][2*n+1];
            x = frunza;
            while (x != 0){

                dif = min (dif,c[t[x]][x]-f[t[x]][x]);
                x = t[x];
            }
            flux += dif;
            /// marim fluxurile
            f[frunza][2*n+1] += dif;
            f[2*n+1][frunza] -= dif;
            x = frunza;
            while (x != 0){
                f[ t[x] ][x] += dif;
                f[x][ t[x] ] -= dif;
                x = t[x];
            }
        }
    }
    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";

    return 0;
}