Cod sursa(job #2469718)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 7 octombrie 2019 21:34:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
#define DIM 205

using namespace std;

ifstream fin  ("harta.in");
ofstream fout ("harta.out");

int n, i, j, x, y, nod, u, minim, fluxsol;
int t[DIM];
int capacitate[DIM][DIM], flux[DIM][DIM];

bitset <DIM> f;
vector <int> L[DIM];
deque <int> q;

int bfs (){
    int nod, vecin;
    f.reset();
    f[0] = 1;
    q.push_back(0);
    while (!q.empty()){
        nod = q.front();
        q.pop_front();
        for (int i=0; i<L[nod].size(); i++){
            vecin = L[nod][i];
            if (f[vecin] == 0 && capacitate[nod][vecin] > flux[nod][vecin]){
                f[vecin] = 1;
                q.push_back(vecin);
                t[vecin] = nod;
            }
        }
    }
    return f[2*n+1];
}

int main(){
    fin >> n;
    for (i=1; i<=n; i++){
        fin >> x >> y;
        capacitate[0][i] = x;
        L[0].push_back(i);
        L[i].push_back(0);
        capacitate[n+i][2*n+1]=y;
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
    }
    for (i=1; i<=n; i++){
        for (j=1; j<=n; j++){
            if (i != j){
                capacitate[i][n+j] = 1;
                L[n+j].push_back(i);
                L[i].push_back(n+j);
            }
        }
    }
    while (bfs()){
        for (i=0; i<L[2*n+1].size(); i++){
            nod = L[2*n+1][i];
            if (capacitate[nod][2*n+1] > flux[nod][2*n+1] && f[nod] == 1){
                minim = capacitate[nod][2*n+1] - flux[nod][2*n+1];
                u = nod;
                while (u){
                    minim = min (minim, capacitate[t[u]][u] - flux[t[u]][u]);
                    u = t[u];
                }
                fluxsol += minim;
                flux[nod][2*n+1] += minim;
                flux[2*n+1][nod] -= minim;
                u = nod;
                while (u){
                    flux[t[u]][u] += minim;
                    flux[u][t[u]] -= minim;
                    u = t[u];
                }
            }
        }
    }
    fout << fluxsol << "\n";
    for (i=1; i<=n; i++){
        for (j=n+1; j<=2*n; j++){
            if (flux[i][j] == 1){
                fout << i << " " << j -n << "\n";
            }
        }
    }
    return 0;
}