Pagini recente » Cod sursa (job #2771183) | Cod sursa (job #2850655) | Cod sursa (job #2396884) | Cod sursa (job #555222) | Cod sursa (job #3188983)
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define maxdim 203
#define max_sum_muchii 16000
int n, in[103], out[103];
int flux[maxdim][maxdim], flux_total;
int rezidual[maxdim][maxdim];
vector<vector<int>> graf;
int ult_nod, primul_nod, capacitate_reziduala;
int parinte[maxdim];
void init(){
for (int i = 0; i<= 2*n+1; i++)
parinte[i] = -1;
}
int exista_drum_crestere(){
init();
queue <int> qu;
qu.push(0);
parinte[primul_nod] = 0;
while (!qu.empty()) {
int nod = qu.front();
qu.pop();
for (int i = 0; i< graf[nod].size(); i++)
{
int nod2 = graf[nod][i];
if (parinte[nod2] == -1 && rezidual[nod][nod2] > 0)
{
// Daca gasim conexiune la final, se termina bfs
if (nod2 == 2*n+1) {
//parinte[nod2] = nod;
return 1;
}
qu.push(nod2);
parinte[nod2] = nod;
}
}
}
return 0;
}
void pt_fiec_nod(int k){
capacitate_reziduala = max_sum_muchii;
parinte[ult_nod] = k;
int nod = ult_nod, prev;
while(nod!= primul_nod && capacitate_reziduala > 0)
{
prev = parinte[nod];
if(rezidual[prev][nod] < capacitate_reziduala)
capacitate_reziduala = rezidual[prev][nod];
nod = prev;
}
nod = ult_nod;
while(nod!= primul_nod && capacitate_reziduala > 0)
{
prev = parinte[nod];
rezidual[nod][prev] += capacitate_reziduala;
rezidual[prev][nod] -= capacitate_reziduala;
nod = prev;
}
flux_total += capacitate_reziduala;
}
void update(){
int i;
//ne uitam la toate drumurile valide pe care le-am gasit si pt fiecare gasim capacitatea reziduala
for (i = n+1; i <= 2*n; i++)
{
pt_fiec_nod(i);
}
}
int main()
{
//nodul de start n punem 0, finalul este 2*n+1
int i,j;
fin >> n;
ult_nod = 2*n+1;
primul_nod = 0;
for (i = 1; i<= n; i++)
fin >> out[i] >> in[i];
graf.resize(maxdim);
for(i = 1; i<= n; i++) //primul rand de noduri
{
//flux[primul_nod][i] = out[i];
rezidual[primul_nod][i] = out[i];
graf[i].push_back(primul_nod);
graf[primul_nod].push_back(i);
for (j = n+1; j<= 2*n; j++)
if(j - n != i)
{
rezidual[i][j] = 1;
graf[i].push_back(j);
graf[j].push_back(i);
}
rezidual[n+i][ult_nod] = in[i];
graf[n+i].push_back(ult_nod);
graf[ult_nod].push_back(n+i);
}
while (exista_drum_crestere())
{
update();
}
fout << flux_total << '\n';
for (i = 1; i<= n; i++)
for (j = n+1; j<= 2*n; j++)
if( i != j - n && rezidual[i][j] == 0)
fout << i << " " << j-n << '\n';
return 0;
}