Pagini recente » Cod sursa (job #310780) | Cod sursa (job #2506461) | Cod sursa (job #674065) | Cod sursa (job #2021222) | Cod sursa (job #2961923)
//
// Created by Carla on 1/7/2023.
//
#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 si cel de vizitate
int tata[202] = {0}, viz[202] = {0};
//nr de muchii
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;
//citim nr de muchii date
in>>n;
//cream un graf complet de n noduri cu ajutorul caruia avem in stanga nodurile propriu zise si in dreapta copiile lor
//adaugam capacitatea 1 pe muchia dintre ele
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;
}
//citim gradele date si pentru fiecare pereche data, pentru gradele de intrare legam de un nod fictiv (-> 0) nodul curent
//si adaugam costul nr.gradelor de intrare, iar pt gradele de iesire legam fiecare nod clona din partea stanga de un nod fictiv
//(-> 2*n+1) si adaugam costul dintre ele nr gradelor de iesire
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, ceea ce va determina nr de noduri
out<<edmonds_karp()<<"\n";
//afisam perechile de noduri care au muchii intre ele
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;
}