Pagini recente » Cod sursa (job #2860925) | Cod sursa (job #2492844) | Cod sursa (job #146513) | Cod sursa (job #2767864) | Cod sursa (job #3190633)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream file_in("harta.in");
ofstream file_out("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>> graph;
int last, first, rezidual_capacity;
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[first] = 0;
while (!qu.empty()) {
int nod = qu.front();
qu.pop();
for (int i = 0; i< graph[nod].size(); i++)
{
int nod2 = graph[nod][i];
if (parinte[nod2] == -1 && rezidual[nod][nod2] > 0)
{
if (nod2 == 2*n+1) {
return 1;
}
qu.push(nod2);
parinte[nod2] = nod;
}
}
}
return 0;
}
void pt_fiec_nod(int k){
rezidual_capacity = max_sum_muchii;
parinte[last] = k;
int nod = last, prev;
while(nod!= first && rezidual_capacity > 0)
{
prev = parinte[nod];
if(rezidual[prev][nod] < rezidual_capacity)
rezidual_capacity = rezidual[prev][nod];
nod = prev;
}
nod = last;
while(nod!= first && rezidual_capacity > 0)
{
prev = parinte[nod];
rezidual[nod][prev] += rezidual_capacity;
rezidual[prev][nod] -= rezidual_capacity;
nod = prev;
}
flux_total += rezidual_capacity;
}
void update(){
int i;
for (i = n+1; i <= 2*n; i++)
{
pt_fiec_nod(i);
}
}
int main()
{
int i,j;
file_in >> n;
last = 2*n+1;
first = 0;
for (i = 1; i<= n; i++)
file_in >> out[i] >> in[i];
graph.resize(maxdim);
for(i = 1; i<= n; i++)
{
rezidual[first][i] = out[i];
graph[i].push_back(first);
graph[first].push_back(i);
for (j = n+1; j<= 2*n; j++)
if(j - n != i)
{
rezidual[i][j] = 1;
graph[i].push_back(j);
graph[j].push_back(i);
}
rezidual[n+i][last] = in[i];
graph[n+i].push_back(last);
graph[last].push_back(n+i);
}
while (exista_drum_crestere())
{
update();
}
file_out << 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)
file_out << i << " " << j-n << '\n';
return 0;
}