Pagini recente » Cod sursa (job #2621114) | Cod sursa (job #1731696) | Cod sursa (job #1326974) | Cod sursa (job #879810) | Cod sursa (job #3189554)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int capacitate[2*100+2][2*100+2];
vector<vector<int>> flux(2*100+2, vector<int>(2*100+2, 0));
int BFS(int NodSursa, int nodDestinatie, vector <int>& parinti, vector<vector<int>>& vecini, int N)
{
fill(parinti.begin(), parinti.end(), -1);
queue <int> OurQueue;
OurQueue.push(NodSursa);
parinti[NodSursa] = 0;
int drum = 0;
while(!OurQueue.empty())
{
int nodCurent = OurQueue.front();
OurQueue.pop();
for(auto vecin: vecini[nodCurent])
{ //daca parintele unui nod este1, este clar ca nodul este nevizitat
if (parinti[vecin]==-1)
{
if (flux[nodCurent][vecin] < capacitate[nodCurent][vecin] )
{
OurQueue.push(vecin);
parinti[vecin] = nodCurent;
// verific daca am gasit lant de la nodul sursa la nodul destinatie
if (vecin == nodDestinatie)
{
drum = 1;
break;
}
}
}
}
}
return drum;
}
int main() {
int N, vin, pleaca;
// vom adauga un nod sursa, un nod destinatie, N noduri IN care
// se ajunge din nodul sursa si N noduri separate DIN CARE se ajunge in
// nodul destinatie
f >> N;
int nodSursa = 2 * N + 1, nodDestinatie = 2 * N + 2;
vector<vector<int>> vecini(2*N+3, vector<int>());
// citim numarul de drumuri si actualizam vectorii corespunzatori
for (int i = 1; i <= N; i++)
{
f >> pleaca >> vin;
capacitate[nodSursa][i] = pleaca;
vecini[i].push_back(nodSursa);
vecini[nodSursa].push_back(i);
// actualizam vectorii si pt celelalte N noduri, din care doar
// se pleaca
capacitate[i+N][nodDestinatie] = vin;
vecini[i+N].push_back(nodDestinatie);
vecini[nodDestinatie].push_back(i+N);
}
// vom adauga muchii intre cele doua 'grupe' de noduri, de la cele in care se ajunge de la
// nodul sursa, la cele care pleaca in nodul destinatie, cu o capacitate maxima egala cu 1
for (int i = 1; i <= N; i++)
{
for (int j = N+1; j<= 2*N; j++ )
{
// nodurile 1..N vor fi de fapt aceleasi cu N+1..2N.
// De aceea, nu vor exista muchii de la 1 la N+1, 2 la N+2 etc
if (j-N != i)
{
capacitate[i][j] = 1;
vecini[i].push_back(j);
vecini[j].push_back(i);
}
}
}
// vom continua prin aplicarea algoritmului Edmonds-Karp
int drum = 1;
// in interiorul functiei BFS vom folosi un vector de parinti pentru a putea reface drumul
// din nodul sursa pana in nodul destinatie
vector<int> parinti(2*N+3, -1);
int fluxTotal = 0;
while(drum)
{
drum = BFS(nodSursa, nodDestinatie, parinti, vecini, N);
if (drum == 1)
{
// refacem drumul pentru a afla bottleneck ul corespunzatorul drumului
int bottleneck = INT_MAX;
int nodActual = nodDestinatie;
while (parinti[nodActual] != 0)
{
int parinte = parinti[nodActual];
if( capacitate[parinte][nodActual] - flux[parinte][nodActual] < bottleneck)
bottleneck = capacitate[parinte][nodActual] - flux[parinte][nodActual];
nodActual = parinte;
}
fluxTotal +=bottleneck;
// dupa ce am aflat care este fluxul maxim, vom actualiza fluxul pe fiecare muchie din lant
nodActual = nodDestinatie;
while(parinti[nodActual] != 0)
{
int parinte = parinti[nodActual];
flux[parinte][nodActual] += bottleneck;
flux[nodActual][parinte] -= bottleneck;
nodActual = parinte;
}
}
}
g << fluxTotal << endl;
for (int i = 1; i <= N; i++ )
for (int j = N+1; j<=2*N; j++)
if (flux[i][j] > 0)
g << i << " " << j-N << endl;
return 0;
}