Pagini recente » Cod sursa (job #1879463) | Cod sursa (job #2902668) | Cod sursa (job #227437) | Cod sursa (job #2734545) | Cod sursa (job #2958495)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
int n, fluxMaxim; //fluxMaxim va reprezenta aici nr de drumuri construite
vector<vector<int>> ramas;
vector<int> visited, dad;
queue<int> coada;
bool construiesteDrum()
{
int i, nodCurent;
while(!coada.empty())
coada.pop();
for(i = 0; i <= 2 * n + 1; i++)
{
dad[i] = -1;
visited[i] = 0;
}
coada.push(0); //pornim de la nodul 0 pt ca ala e nodul de start (nodul 0 fiind nodul de start creat de noi)
visited[0] = 1;
while(!coada.empty())
{
nodCurent = coada.front();
coada.pop();
if (nodCurent == 2 * n + 1) //daca am ajuns la 2 * n + 1 care e destinatia inseamna ca am reusit sa creem un drum
return true;
for(i = 1; i <= 2 * n + 1; i++) //parcurgem toate nodurile si vedem daca se poate ajunge din nodul curent in respectivul nod (adica sa nu fie vizitat si sa mai avem capacitate ramasa)
if(ramas[nodCurent][i] > 0 && visited[i] == 0)
{
visited[i] = 1;
dad[i] = nodCurent;
coada.push(i);
}
}
return false; //daca se ajunge aici inseamna ca if(nodCurent == n) nu a fost apelat, deci nu s-a ajuns pana la destinatie, deci nu am reusit sa creem un drum
}
void calculeazaFluxMax()
{
int i, fiu, nodCurent, j, bootleNeck;
vector<int> drum;
while(construiesteDrum()) //daca nu mai gasim un drum ne oprim
{
for(i = n + 1; i < 2 * n + 1; i++) //incercam sa reconstruim drumurile
{
if(ramas[i][2 * n + 1] > 0 && visited[i] == 1) //inseamna ca din nodul i la care suntem acuma s-a transportat o anumita cantitate in nodul final
{
fiu = i;
drum.clear(); //daca nu facem asta ramane din forul anterior
drum.push_back(2 * n + 1);
drum.push_back(fiu);
nodCurent = dad[fiu];
while (nodCurent != 0) //mergem inapoi pe traseu si reconstruim drumul
{
drum.push_back(nodCurent);
nodCurent = dad[nodCurent];
}
drum.push_back(0);
bootleNeck = INT_MAX;
for(j = drum.size() - 1; j >= 1; j--) //parcurgem pe invers pt ca noi in drum am pus elementele pornind de la destinatie spre start
bootleNeck = min(bootleNeck, ramas[drum[j]][drum[j - 1]]);
fluxMaxim += bootleNeck;
for(j = drum.size() - 1; j >= 1; j--)
{
ramas[drum[j]][drum[j - 1]] -= bootleNeck; //scadem capacitatea ramase pt drumurile prin care am trecut
ramas[drum[j - 1]][drum[j]] += bootleNeck; //in cazul drumurilor reversed crestem aceasta capacitate
}
}
}
}
}
int main()
{
int i, j, nrOut, nrIn;
in >> n;
dad.resize(2 * n + 2);
visited.resize(2 * n + 2);
ramas.resize(2 * n + 2);
for(i = 0; i <= 2 * n + 1; i++)
ramas[i].resize(2 * n + 2, 0);
for(i = 1; i <= n; i++)
{
in >> nrOut >> nrIn;
ramas[0][i] = nrOut; //creem un nod de start, pt care pleaca catre fiecare nod o muchie cu capacitatea egala cu cate muchii pleaca din nodul respectiv mai departe
ramas[n+i][2 * n + 1] = nrIn; //creem un nod destinatie, in care intra pt fiecare nod o muchie cu capacitatea egala cu cate muchii intra in nodul respectiv
for (j = 1; j <= n; j++)
if (j != i)
ramas[i][n + j] = 1;
}
calculeazaFluxMax();
out << fluxMaxim << '\n'; //nr de drumuri construite
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(i != j && ramas[i][n + j] == 0) //inseamna ca am construit drum intre nodul i si j daca capacitatea ramasa e 0
out << i << " " << j << '\n';
return 0;
}