Cod sursa(job #2084958)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 9 decembrie 2017 13:42:46
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("harta.in");
ofstream out ("harta.out");
const int dim = 105;
int a,s,f,b,n,sol,vecin,x,minim;
int graf[dim*2],vec[2*dim],tata[2*dim];
int cap[dim][dim*2], flux[dim][dim*2];
vector<int>v[2*dim];
bool bfs (void) {
    for (int i = s; i <= f; i ++) {
        graf[i] = 0;
    }
    bool ok = false;
    vec[1] = s;
    graf[s] = 1;
    tata[s] = -1;
    for (int st = 1, dr = 1; st <= dr; st ++) {
        a = vec[st];
        for (int i = 0; i < v[a].size(); i ++) {
            b = v[a][i];
            if (cap[a][b] > flux[a][b] && graf[b] == 0) {
                if (b != f) {
                    vec[++dr] = b;
                    graf[b] = 1;
                    tata[b] = a;
                }
                else{
                    ok = true;
                    tata[b] = a;
                }
            }
        }
    }
    return ok;
}
int main (void) {
    in >> n;
    s = 0; f = n * 2 + 1;
    for (int i = 1; i <= n; i ++) {
        in >> a >> b;
        v[s].push_back (i);
        v[i].push_back (s);
        cap[s][i] = a;
        v[i+n].push_back (f);
        v[f].push_back (i+n);
        cap[i+n][f] = b;
        sol += a;
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (i != j) {
                v[i].push_back (j+n);
                v[j+n].push_back (i);
                cap[i][j+n] = 1;
            }
        }
    }
    while (bfs()) {
        for (int i = 0; i < v[f].size(); i ++) {
            vecin = v[f][i];
            if (cap[vecin][f] > flux[vecin][f]) {
                minim = cap[vecin][f] - flux[vecin][f];
                x = vecin;
                while (tata[x] != -1) {
                    minim = min(minim, cap[tata[x]][x] - flux[tata[x]][x]);
                    x = tata[x];
                }
                x = vecin;
                while (tata[x] != -1) {
                    flux[tata[x]][x] += minim;
                    flux[x][tata[x]] -= minim;
                    x = tata[x];
                }
                flux[vecin][f] += minim;
                flux[f][vecin] -= minim;
            }
        }
    }
    out << sol <<"\n";
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (flux[i][j+n] == 1) {
                out << i <<" "<< j<<"\n";
            }
        }
    }
    return 0;
}