Pagini recente » Cod sursa (job #1882854) | Cod sursa (job #1566261) | Cod sursa (job #1293196) | Diferente pentru info-oltenia-2018/individual/clasament/11-12 intre reviziile 4 si 2 | Cod sursa (job #2962364)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,flux;
vector<vector<int>> adiacenta, capacitate;
vector<bool> vizitat;
vector<int> tata;
bool bfs(){
// cu bfs cautam in graful rezidual daca exista un drum din sursa pana in destinatie
queue<int> coada;
vizitat.clear();
tata.clear();
vizitat.resize(2*n+2,false);
tata.resize(2*n+2,0);
coada.push(0);
vizitat[0]=true;
while(!coada.empty()){
int nod=coada.front();
coada.pop();
if(nod==2*n+1)
return true;
for (int i = 0; i < adiacenta[nod].size(); ++i) {
if(!vizitat[adiacenta[nod][i]] && capacitate[nod][adiacenta[nod][i]]>0){
tata[adiacenta[nod][i]]=nod;
coada.push(adiacenta[nod][i]);
vizitat[adiacenta[nod][i]]=true;
}
}
}
return false;
}
int main(){
// Complexitatea este de O(n*m*m)
// Ideea se bazeaza pe algoritmul Edmonds-Karp
// Dublam fiecare nod si le memoram de la 1 la n si de la n+1 la 2*n
// Adaugam un nod sursa numerotat cu 0 si un nod destinatie 2*n+1
int x,y;
f>>n;
adiacenta.resize(2*n+2);
capacitate.resize(2*n+2,vector<int>(2*n+2,0));
// Adaugam muchie intre sursa si toate nodurile (prima multime) cu capacitate gradul pentru iesire
// Si muchie intre toate nodurile (a doua multime) si destinatie cu capacitate gradul pentru intrare
// Apoi adaug muchie de la orice nod din prima multime la orice alt nod din a doua multime cu capacitatea 1
for (int i = 1; i <= n; ++i) {
f>>x>>y;
capacitate[0][i]=x;
capacitate[n+i][2*n+1]=y;
adiacenta[0].push_back(i);
adiacenta[i].push_back(0);
adiacenta[n+i].push_back(2*n+1);
adiacenta[2*n+1].push_back(n+i);
for (int j = n+1; j <= 2*n; ++j) {
if(n+i!=j){
adiacenta[i].push_back(j);
adiacenta[j].push_back(i);
capacitate[i][j]=1;
}
}
}
while(bfs()){ // cat timp pot ajunge de la sursa la destinatie
for (int i = 0; i < adiacenta[2*n+1].size(); ++i) {
if(vizitat[adiacenta[2*n+1][i]]){ // am gasit un drum pana in destinatie care contine acest nod
tata[2*n+1]=adiacenta[2*n+1][i];
int minim=INT_MAX;
for (int j = 2*n+1; j !=0 ; j=tata[j]) { // calculam minimul lantului
minim=min(minim,capacitate[tata[j]][j]);
}
for (int j = 2*n+1; j !=0 ; j=tata[j]) { // actualizam graful rezidual
capacitate[tata[j]][j] -= minim;
capacitate[j][tata[j]] += minim;
}
flux+= minim;
}
}
}
g<<flux<<'\n'; // fluxul maxim este numarul de muchii adaugate
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < adiacenta[i].size(); ++j) {
if(capacitate[i][adiacenta[i][j]]==0) // muchiile sunt cele saturate
g<<i<<' '<<adiacenta[i][j]-n<<'\n';
}
}
return 0;
}