Pagini recente » Cod sursa (job #1233158) | Cod sursa (job #2724324) | Cod sursa (job #1837451) | Cod sursa (job #1276252) | Cod sursa (job #2962037)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, in[101], out[101], capGrafRezidual[202][202], newSource, newDestination, tata[202];
vector<int> listaAdiacenta[202];
bool bfs() {
vector<bool> vizitat;
queue<int> q;
vizitat.resize(newDestination + 1);
q.push(newSource);
vizitat[newSource] = true;
while(!q.empty()){
int nod = q.front();
q.pop();
for(auto vecin : listaAdiacenta[nod]){
// Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el (capacitatea e mai mare decat 0)
if(!vizitat[vecin] && capGrafRezidual[nod][vecin]){
// Este updatat vectorul tata pentru a putea reconstrui drumul de ameliorare
tata[vecin] = nod;
vizitat[vecin] = true;
q.push(vecin);
// Daca vecinul este destinatia atunci am gasit un drum bun
// BFS-ul este optimizat pentru ca el se incide direct cand vecinul este destinatia
if(vecin == newDestination)
return true;
}
}
}
// Daca ajung aici nu mai sunt drumuri bune
return false;
}
int edmondsKarp()
{
int raspuns = 0;
// Cat timp mai gasesc un drum pana la destinatie pe care pot adauga flow
while(bfs()) {
int nod = newDestination, bottleNeck = 1000000000;
while(nod != newSource) {
int parinte = tata[nod];
if(capGrafRezidual[parinte][nod] < bottleNeck) {
// Este calculata valoarea minima de pe drumul respectiv (bottleNeck), de la destinatie la sursa
// folosind vectorul tata
bottleNeck = capGrafRezidual[parinte][nod];
}
nod = parinte;
}
// Adaug la toate muchiile de pe drum flow-ul maxim
nod = newDestination;
while(nod != newSource) {
int parinte = tata[nod];
capGrafRezidual[parinte][nod] -= bottleNeck; // Drum direct in graful rezidual
capGrafRezidual[nod][parinte] += bottleNeck; // Drum invers in graful rezidual
nod = parinte;
}
// Adaug flow-ul gasit la raspuns
raspuns += bottleNeck;
}
return raspuns;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> in[i] >> out[i];
newSource = 0;
newDestination = 2 * n + 1;
// Sparg nodurile in doua unul care e conectat de sursa si unul care e conectat de destinatie
// Muchii de la sursa la noduri
for(int i = 1; i <= n; ++i) {
listaAdiacenta[newSource].push_back(i);
capGrafRezidual[newSource][i] = in[i];
}
// Muchii de la noduri la destinatie
for(int i = 1; i <= n; ++i) {
listaAdiacenta[n + i].push_back(newDestination);
capGrafRezidual[n + i][newDestination] = out[i];
}
// Muchiile intre noduri
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j) {
listaAdiacenta[i].push_back(n + j);
listaAdiacenta[n + j].push_back(i);
capGrafRezidual[i][n + j] = 1;
}
fout << edmondsKarp() << '\n';
//Muchiile construite
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(capGrafRezidual[n+j][i] == 1)
fout << i << " " << j << '\n';
return 0;
}