Cod sursa(job #1822564)

Utilizator BugirosRobert Bugiros Data 5 decembrie 2016 09:47:51
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n;

const int INF = 1 << 29;


const int MAXN = 105;

vector<int> vecini[2 * MAXN];
int capacitate[2 * MAXN][2 * MAXN];//Atentie! trebuie cu matrice de adiacenta deoarece avem nevoie in O(1) fluxul dintre oricare doua noduri
int flux[2 * MAXN][2 * MAXN];//Atentie! trebuie cu matrice de adiacenta deoarece avem nevoie in O(1) capacitatea dintre oricare doua noduri

int sursa;
int destinatie;

bool vizitat[2 * MAXN];
int tata[2 * MAXN];

void citire()
{
    in >> n;
    sursa = 0;
    destinatie = 2 * n + 1;
    for (int i = 1;i <= n;++i)
    {
        int intra,iese;
        in >> intra >> iese;
        vecini[0].push_back(i);
        vecini[i].push_back(0);
        capacitate[0][i] = intra;

        vecini[i + n].push_back(2 * n + 1);
        vecini[2 * n + 1].push_back(i + n);
        capacitate[i + n][2 * n + 1] = iese;

        for (int j = n + 1;j <= 2 * n;++j)
            if (i != j - n)
            {
                vecini[i].push_back(j);
                vecini[j].push_back(i);
                capacitate[i][j] = 1;
            }
    }
}

//intoarce adevarat daca s-a mai gasit un drum de ameliorare
bool BFS()//construieste arborele BFS
{
    for (int i = 0;i <= 2 * n + 1;++i)
        vizitat[i] = false;
    int coada[2 * MAXN] = {0};
    int p = 1,q = 1;
    coada[1] = sursa;
    vizitat[sursa] = true;
    while (p <= q)
    {
        int nod = coada[p];
        ++p;
        if (nod == destinatie)//arborele il construim fara destinatie
            continue;
        for (unsigned int i = 0;i < vecini[nod].size();++i)
        {
            int vecin = vecini[nod][i];
            if (vizitat[vecin] || flux[nod][vecin] == capacitate[nod][vecin])
                continue;
            coada[++q] = vecin;
            vizitat[vecin] = true;
            tata[vecin] = nod;
        }
    }

    return vizitat[destinatie];
}
int main()
{
    citire();
    int fluxmaxim = 0;
    while(BFS())
        for(unsigned int i = 0;i < vecini[destinatie].size();++i)
        {
            int vecin = vecini[destinatie][i];
            if (!vizitat[vecin] || flux[vecin][destinatie] == capacitate[vecin][destinatie])
                continue;
            //influx -> fluxul minim care se adauga(sau daca e negativ, se scade) pe drumul de ameliorare
            int influx = INF;
            int nod = destinatie;
            tata[destinatie] = vecin;//legam temporar la frunza destinatie pentru parcurgere
            while(nod != sursa)//cautam minimul de influx
            {
                if (capacitate[tata[nod]][nod] - flux[tata[nod]][nod] < influx)
                    influx = capacitate[tata[nod]][nod] - flux[tata[nod]][nod];
                nod = tata[nod];
            }
            if (influx == 0)
                continue;
            nod = destinatie;
            while(nod != sursa)//adaugam influxul
            {
                flux[tata[nod]][nod] += influx;
                flux[nod][tata[nod]] -= influx;
                nod = tata[nod];
            }
            fluxmaxim += influx;
        }
    out << fluxmaxim << '\n';
    for (int i = 1;i <= n;++i)
        for (int j = n + 1;j <= 2 * n;++j)
            if (flux[i][j] != 0)
                out << i << ' ' << j - n << '\n';

    return 0;
}