Pagini recente » Cod sursa (job #3197886) | Cod sursa (job #140418) | Cod sursa (job #190886) | Cod sursa (job #2513559) | Cod sursa (job #3188442)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int main()
{
int n;
f >> n;
// vrem sa construim o retea corespunzatoare grafului pe care vrem sa-l construim
// luam un graf bipartit avand in ambele parti cate o copie a nodurile din graful pe care vrem sa-l construim
// nodul 0 = nodul de start
// nodul n * 2 + 1 = nodul final
// de la nodul de start la nodurile noastre vom avem muchii cu capacitatea = gradele de iesire
// la nodul final de la noduri vom avea muchii cu capacitatea = gradele de intrare
int last = n * 2 + 1;
vector <vector <int>> vecini(last + 1, vector <int> ());
vector <vector <int>> capacitate(last + 1, vector <int> (last + 1, 0));
vector <vector <int>> flux(last + 1, vector <int>(last + 1, 0));
for(int i = 1; i <= n; i++)
{
int in, out;
f >> out >> in;
vecini[0].push_back(i);
vecini[i].push_back(0);
capacitate[0][i] = out;
vecini[last].push_back(n + i);
vecini[n + i].push_back(last);
capacitate[i + n][last] = in;
}
f.close();
// construim muchiile intre potentialii vecini de capacitate 1
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
{
vecini[i].push_back(j + n);
vecini[j + n].push_back(i);
capacitate[i][j + n] = 1;
}
// determinam fluxul maxim pe reteaua construita
bool avemDrumDeCrestere = true;
while(avemDrumDeCrestere)
{
avemDrumDeCrestere = false;
//cautam cu bfs un lant de la nodul de start la cel de finish in care sa putem creste fluxul
queue <int> q;
vector <int> tata(last + 1); // daca muchia intoarce flux => -tata
vector <bool> vis(last + 1, false);
//initializare vector de tati
for(int i = 0; i <= last; i++)
tata[i] = i;
q.push(0);
vis[0] = true;
while(!q.empty())
{
int nod = q.front();
q.pop();
for(int i = 0; i < vecini[nod].size(); i++)
{
int vecin = vecini[nod][i];
if(capacitate[nod][vecin] > flux[nod][vecin] && !vis[vecin])
{
q.push(vecin);
vis[vecin] = true;
tata[vecin] = nod;
// daca am gasit un lant pana la nodul final
if(vecin == last)
{
avemDrumDeCrestere = true;
break;
}
}
}
}
// daca avem drum
if(avemDrumDeCrestere)
{
// il parcurgem si aflam fluxul maxim pe care putem sa-l pusham pe toate muchiile
int nodCurent = last;
int fluxMaxim = 100; // fluxul nostru maxim pe un drum oricum e 1
while(nodCurent != 0)
{
int predecesor = tata[nodCurent];
if(fluxMaxim > capacitate[predecesor][nodCurent] - flux[predecesor][nodCurent])
fluxMaxim = capacitate[predecesor][nodCurent] - flux[predecesor][nodCurent];
nodCurent = predecesor;
}
// il parcurgem si pusham fluxul respectiv pe fiecare muchie
nodCurent = last;
while(nodCurent != 0)
{
int predecesor = tata[nodCurent];
flux[predecesor][nodCurent] += fluxMaxim;
flux[nodCurent][predecesor] -= fluxMaxim;
nodCurent = predecesor;
}
}
}
// avem muchii = suma gradelor de intrare / iesire
int m = 0;
for(int i = 1; i <= n; i++)
m += capacitate[0][i];
g << m << endl;
// parcurgem reteaua si vedem care muchii au fost saturate => nodurile au devenit vecini
for(int i = 1; i <= n; i++)
for(int j = 1 + n; j <= n * 2; j++)
if(flux[i][j])
g << i << ' ' << j - n << endl;
g.close();
return 0;
}