Cod sursa(job #1253381)

Utilizator diana97Diana Ghinea diana97 Data 1 noiembrie 2014 10:52:21
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("harta.in");
ofstream g ("harta.out");

const int NMAX = 2 * 100 + 2;
int n, sursa, destinatie;
bool vizitat[NMAX];
int tata[NMAX];
int cost[NMAX][NMAX];
int F[NMAX][NMAX];
vector <int> graf[NMAX];
vector < pair <int, int> > sol;

void initializeaza() {
    f >> n;
    sursa = 0;
    destinatie = 2 * n + 1;

    int in, out;
    for (int i = 1; i <= n; i++) {
        f >> in >> out;

        graf[sursa].push_back(i);
        graf[i].push_back(sursa);
        cost[sursa][i] += in;

        graf[i + n].push_back(destinatie);
        graf[destinatie].push_back(i + n);
        cost[i + n][destinatie] += out;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j) {
                graf[i].push_back(j + n);
                graf[j + n].push_back(i);
                cost[i][j + n]++;
            }
}

bool BFS() {
    int i, nod, fiu, l;
    queue <int> Q;

    for (int i = 0; i <= NMAX; i++) vizitat[i] = false, tata[i] = 0;

    Q.push(sursa); vizitat[sursa] = true;

    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        if (nod != destinatie) {
            int l = graf[nod].size();
            for (int i = 0; i < l; i++) {
                fiu = graf[nod][i];
                if (!vizitat[fiu] && F[nod][fiu] < cost[nod][fiu]) {
                    Q.push(fiu);
                    vizitat[fiu] = true;
                    tata[fiu] = nod;
                }
            }
        }
    }

    return vizitat[destinatie];
}

void flux() {
    int l, nod, rez, ant;
    while(BFS()) {
        l = graf[destinatie].size();
        for (int i = 0; i < l; i++) {
            nod = graf[destinatie][i];
            rez = cost[nod][destinatie] - F[nod][destinatie];
            while (nod != sursa) {
                ant = tata[nod];
                rez = min(rez, cost[ant][nod] - F[ant][nod]);
                nod = ant;
            }

            if (rez == 0) continue;

            nod = graf[destinatie][i];
            F[nod][destinatie] += rez;
            F[destinatie][nod] -= rez;

            while (nod != sursa) {
                ant = tata[nod];
                F[ant][nod] += rez;
                F[nod][ant] -= rez;
                nod = ant;
            }
           // sol += rez;
        }
    }
  //  cout << sol << '\n';
}

void scrie() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (F[i][j + n] > 0) sol.push_back(make_pair(i, j));
    g << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++) g << sol[i].first << ' ' << sol[i].second << '\n';
}


int main() {
    initializeaza();
    flux();
    scrie();
}