Pagini recente » Cod sursa (job #76071) | Cod sursa (job #1173172) | Cod sursa (job #874717) | Cod sursa (job #3230205) | Cod sursa (job #3189831)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NR_MAX_NODURI = 301;
int grafFlux[NR_MAX_NODURI][NR_MAX_NODURI], parintiNoduri[NR_MAX_NODURI];
bool nodVizitat[NR_MAX_NODURI];
//citire
void citesteGraf(int& numarNoduri)
{
fin >> numarNoduri;
int muchiiOut, muchiiIn;
for (int i = 1; i <= numarNoduri; i++)
{
fin >> muchiiOut >> muchiiIn;
grafFlux[0][i] = muchiiOut;
grafFlux[i + numarNoduri][numarNoduri * 2 + 1] = muchiiIn;
}
for (int i = 1; i <= numarNoduri; i++)
for (int j = 1; j <= numarNoduri; j++)
if (i != j) grafFlux[i][j + numarNoduri] = 1;
}
//BFS
bool parcurgereBFS(int numarNoduri)
{
queue<int> coada;
for (int i = 0; i <= numarNoduri; i++)
{
nodVizitat[i] = false;
parintiNoduri[i] = -1;
}
coada.push(0);
nodVizitat[0] = true;
while (!coada.empty())
{
int nodCurent = coada.front();
coada.pop();
for (int i = 0; i <= numarNoduri; i++)
{
if (grafFlux[nodCurent][i] > 0 && !nodVizitat[i])
{
coada.push(i);
nodVizitat[i] = true;
parintiNoduri[i] = nodCurent;
if (i == numarNoduri)
return true;
}
}
}
return false;
}
//flux maxim in graf
int calculeazaFluxMaxim(int numarNoduri)
{
int valoareFluxMaxim = 0;
while (parcurgereBFS(numarNoduri))
{
for (int nodCurent = 1; nodCurent < numarNoduri; nodCurent++)
{
if (grafFlux[nodCurent][numarNoduri] > 0 && nodVizitat[nodCurent])
{
int nodPenultim = nodCurent;
//construim calea curenta
vector<int> caleCurenta;
caleCurenta.push_back(numarNoduri);
caleCurenta.push_back(nodPenultim);
//parintele penultimului
int nodParinte = parintiNoduri[nodPenultim];
while (nodParinte != -1)
{
caleCurenta.push_back(nodParinte);
nodParinte = parintiNoduri[nodParinte];
}
//capacitatea minima
int bottleneck = 2;
for (int i = 1; i < caleCurenta.size(); i++)
bottleneck = min(bottleneck, grafFlux[caleCurenta[i]][caleCurenta[i - 1]]);
//actualizam fluxul maxim
valoareFluxMaxim += bottleneck;
for (int i = 1; i < caleCurenta.size(); i++) //si matricea de fluxuri
{
grafFlux[caleCurenta[i]][caleCurenta[i - 1]] -= bottleneck;
grafFlux[caleCurenta[i - 1]][caleCurenta[i]] += bottleneck;
}
}
}
}
return valoareFluxMaxim;
}
//afisare
void scrieRezultate(int numarNoduri)
{
fout << calculeazaFluxMaxim(2 * numarNoduri + 1) << "\n";
for (int i = 1; i <= numarNoduri; i++)
for (int j = numarNoduri + 1; j <= numarNoduri * 2; j++)
if (grafFlux[j][i] != 0)
fout << i << " " << j - numarNoduri << "\n";
}
int main()
{
int numarNoduri;
citesteGraf(numarNoduri);
scrieRezultate(numarNoduri);
return 0;
}