Pagini recente » Cod sursa (job #2697496) | Cod sursa (job #2036461) | Cod sursa (job #2544908) | Cod sursa (job #2698498) | Cod sursa (job #3188195)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int nr_noduri, sursa, destinatie, ies , intra, nr_muchii;
//Ford-Fulkerson, bazat pe BFS
int bfs(int sursa, int destinatie, vector<int>& tata, vector<vector<int>>& muchii,
vector<vector<int>>& capacitate, vector<vector<int>>& flux){
for(int i = 0; i < tata.size(); i++)
tata[i] = -1;
int f_min = INT_MAX;
tata[sursa] = sursa;
queue<int> q;
q.push(sursa);
// verific toate muchile (sursa - noduri coloana 1, apoi noduri coloana1- noroduri coloana 2, si noduri coloana 2-destinatie)
// calculand fluxul minim pe care il trimit, de la s la t
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < muchii[x].size(); i++){
int vecin = muchii[x][i];
if(tata[vecin] == -1 && flux[x][vecin] < capacitate[x][vecin]){
tata[vecin] = x;
if(f_min > capacitate[x][vecin] - flux[x][vecin])
f_min = capacitate[x][vecin] - flux[x][vecin];
if(destinatie == vecin)
return f_min;
q.push(vecin);
}
}
}
return 0;
}
int main(){
f >> nr_noduri;
sursa = 0;
destinatie = 2 * nr_noduri + 1;
vector<int> tata(destinatie + 1, -1);
vector<vector<int>> muchii(destinatie + 1);
vector<vector<int>> flux(destinatie + 1, vector<int>(destinatie + 1, 0));
vector<vector<int>> capacitate(destinatie + 1, vector<int>(destinatie + 1, 0));
for(int i = 1; i <= nr_noduri; i++){
f >> ies >> intra;
muchii[i].push_back(sursa); // sursa are muchie cu fiecare nod 1..n din coloana 1
muchii[sursa].push_back(i);
capacitate[sursa][i] = ies; // cat trec pe muchii de la sursa la nodurile 1..n din coloana 1
for(int j = 1; j <= nr_noduri; j++)
if(i != j){
muchii[i].push_back(j + nr_noduri); // fiecare nod 1..n din coloana 1 are muchie cu nodurile n+1..n+n din coloana 2
muchii[j + nr_noduri].push_back(i); // si invers , dar fara bucla ( daca n= 4, nu am muchie 1-5, 2-6..)
capacitate[i][j + nr_noduri] = 1; // capacitatile intre fiecare = 1
}
muchii[i + nr_noduri].push_back(destinatie); // fiecare nod n+1..n+n din coloana 2 are legatura cu destinatia
muchii[destinatie].push_back(i + nr_noduri);
capacitate[i + nr_noduri][destinatie] = intra; // capacitatea fiind nr de muchii care intra
}
nr_muchii = 0;
while(1){ // cat timp mai am ce sa trimit
int f = bfs(sursa, destinatie, tata, muchii, capacitate, flux); // cat pot trimite minim de la s la t
if(f){
nr_muchii += f;
// parcurs drumul t->s ajutandu-ma de vectorul de tati pentru a completa matricea de flux
int x = destinatie;
while(x != sursa){
int y = tata[x]; // adaug la fiecare pas cantitatea de marfa trimisa de la s la t
flux[y][x] += f; // pe fiecare muchie care alcatuieste acest drum
flux[x][y] -= f; // indic cat pot trimite si invers
x = y;
}
}
else
break;
}
g << nr_muchii << endl;
for(int i = 1; i <= nr_noduri; i++)
for(int j = 1; j <= nr_noduri; j++)
if(flux[i][j + nr_noduri])
g << i << ' ' << j << endl;
return 0;
}