Pagini recente » Cod sursa (job #2227887) | Cod sursa (job #1562829) | Cod sursa (job #407232) | Cod sursa (job #1523761) | Cod sursa (job #2961057)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
///capacity -> capacitatea muchiei,
int capacity[202][202];
///l -> vecorul care retine graful + graful rezidual
vector<int> l[2002];
///vectorul de parinti
int tata[202] = {0}, viz[202] = {0};
int n;
int bfs()
{
queue<int> q;
///rescriem valorile din vectorul de tati si cel de vizitate
memset(tata, 0, sizeof(tata));
memset(viz, 0, sizeof(viz));
q.push(0);
viz[0] = 1;
tata[0] = -1;
///BFS clasic
while(!q.empty())
{
int u = q.front();
q.pop();
///iesim cu 1 daca am ajuns la nodul 2*n+1
if(u == 2*n+1)
return 1;
for(int i = 0; i < l[u].size(); i++)
{
int v = l[u][i];
///inseamna ca nu e vizitat
if(capacity[u][v] > 0 && !viz[v])
{
///updatam vectorul de tati pentru a avea drumul
tata[v] = u;
///setam nodul ca vizitat
viz[v] = 1;
q.push(v);
}
}
}
return 0;
}
///pentru a optimiza programul efectuam algoritmul lui Edmonds Karp atata timp
///cat prin parcurerea BFS putem ajunge din nodul 1 in nodul n, ceea ce inseamna
///ca estista un drum pe care fluxul rezidual sa fie minim si mai am capacitate
///disponibila pe muchii pentru a mari fluxul
int edmonds_karp()
{
///maxim -> fluxul maxim, minim -> fluxul minim rezidual gasit dupa parcurgerea BFS
///u -> nodul curent, v -> vecinul acestuia
int maxim = 0, minim, u, v;
///cat timp prin parcurgerea BFS ajung din nodul 1 in nodul n
while(bfs())
{
///iterez prin vecinii nodului n(final)
for(int i = 0; i < l[2*n+1].size(); i++)
{
u = l[2*n+1][i];
///daca mai am capacitate disponibila pe muchia dintre noduri
///si nodul e vizitat atunci calculam fluxul minim rezidual
if(capacity[u][2*n+1] > 0 && viz[u])
{
///in BFS am pastrat in vectorul de tati drumul gasit pentru transmiterea fluxului
///iar acum parcurgem acel drum pentru a gasi minimul si pentru a reactualiza capacitatile
///de pe muchii, in functie de cum apar in parcurgere
minim = capacity[u][2*n+1];
while(tata[u] != -1)
{
v = tata[u];
minim = min(minim, capacity[v][u]);
u = v;
}
maxim += minim;
u = l[2*n+1][i];
capacity[u][2*n+1] -= minim;
capacity[2*n+1][u] += minim;
while(tata[u] != -1)
{
v = tata[u];
capacity[v][u] -= minim;
capacity[u][v] += minim;
u = v;
}
}
}
}
return maxim;
}
int main()
{
int di, de;
in>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
{
l[i].push_back(j+n);
l[j+n].push_back(i);
capacity[i][j+n] = 1;
}
for(int i = 1; i <= n; i++)
{
in>>di>>de;
l[0].push_back(i);
l[i].push_back(0);
capacity[0][i] = di;
l[2*n+1].push_back(i+n);
l[i+n].push_back(2*n+1);
capacity[i+n][2*n+1] = de;
}
///calculam fluxul maxim cu ajutorul algoritmului Edmonds Karp
out<<edmonds_karp()<<"\n";
for(int i = 1; i <= n; i++)
for(int j = n+1; j <= 2*n; j++)
if(capacity[j][i] == 1)
out<<i<<" "<<j-n<<"\n";
return 0;
}