Pagini recente » Cod sursa (job #191986) | Cod sursa (job #723266) | Cod sursa (job #1779666) | Cod sursa (job #456646) | Cod sursa (job #2962159)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
int n, numarNoduri, numarDrumuri;
int sursa, destinatie;
int capacitate[201][201];
int flux[201][201];
bool vizitat[201];
int tata[201];
vector<vector<int>> vecini;
void Citire()
{
ifstream f("harta.in");
int numarIntrari, numarIesiri;
f >> n;
/**
* - n noduri pentru muchiile de intrare (legate de nodul de sursa)
* - n noduri pentru muchiile de iesire (legate de nodul final)
* - un nod de sursa si un nod de final
*
* Am noduri de la 0 la numarNoduri - 1
*/
numarNoduri = 2 * n + 2;
sursa = 0;
destinatie = numarNoduri - 1;
vecini.resize(numarNoduri);
// Creez matricea capacitate
for(int nod = 1; nod <= n; nod++)
{
f >> numarIntrari >> numarIesiri;
capacitate[sursa][nod] = numarIntrari;
capacitate[nod + n][destinatie] = numarIesiri;
}
}
void FormareMuchii()
{
// Formez muchiile de la sursa la nodurule 1 .. n
for(int nod = 1; nod <= n; nod++)
{
vecini[sursa].push_back(nod);
vecini[nod].push_back(sursa);
}
// Formez muchiile de la nodurile (n + 1) .. (2 * n + 1) la nodul destinatie
for(int nod = n + 1; nod < numarNoduri - 1; nod++)
{
vecini[nod].push_back(destinatie);
vecini[destinatie].push_back(nod);
}
// Formez muchiile intre nodurile 1 .. n si nodurile (n + 1) .. (2 * n + 1)
for(int nod = 1; nod <= n; nod++)
for(int nodVecin = n + 1; nodVecin < numarNoduri - 1; nodVecin++)
{
if(nodVecin - nod == n)
continue;
vecini[nod].push_back(nodVecin);
vecini[nodVecin].push_back(nod);
// Setez capacitatea pe 1
capacitate[nod][nodVecin] = 1;
}
}
void ResetareVizitat()
{
for(int nod = 0; nod < numarNoduri; nod++)
{
vizitat[nod] = false;
}
}
int Bfs()
{
queue<int> coada;
ResetareVizitat();
vizitat[sursa] = true;
coada.push(sursa);
while(!coada.empty())
{
int nodCurent = coada.front();
coada.pop();
for(auto nodVecin : vecini[nodCurent])
{
if(!vizitat[nodVecin] && flux[nodCurent][nodVecin] < capacitate[nodCurent][nodVecin])
{
vizitat[nodVecin] = true;
tata[nodVecin] = nodCurent;
coada.push(nodVecin);
if(nodVecin == destinatie)
return 1;
}
}
}
return 0;
}
void ActualizareFlux(int nod)
{
if(nod == sursa)
return;
int nodTata = tata[nod];
flux[nodTata][nod] += 1;
flux[nod][nodTata] -= 1;
ActualizareFlux(nodTata);
}
int FluxRamasMinim(int nod)
{
if(nod == sursa)
return 1000000000;
int nodTata = tata[nod];
int fluxRamas = capacitate[nodTata][nod] - flux[nodTata][nod];
return min(fluxRamas, FluxRamasMinim(nodTata));
}
void DeterminareSolutie()
{
while(Bfs())
{
for(auto nodVecin : vecini[destinatie])
{
if(!vizitat[nodVecin] || FluxRamasMinim(destinatie) == 0)
continue;
numarDrumuri++;
ActualizareFlux(destinatie);
}
}
}
void Afisare()
{
ofstream g("harta.out");
g << numarDrumuri << endl;
for(int nod = 1; nod <= n; nod++)
for(int nodVecin = n + 1; nodVecin < numarNoduri; nodVecin++)
{
if(flux[nod][nodVecin] == 1)
g << nod << " " << nodVecin - n << endl;
}
}
int main()
{
Citire();
FormareMuchii();
DeterminareSolutie();
Afisare();
return 0;
}