Pagini recente » Cod sursa (job #177143) | Cod sursa (job #1534657) | Cod sursa (job #1498254) | Cod sursa (job #2492157) | Cod sursa (job #3188804)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int nod_start, nod_final;
vector<vector<int>> flow(202, vector<int>(202, 0));
vector<vector<int>> capacitate(202, vector<int>(202, 0));
vector<int> temp_flow(202, 0); //pe arc
vector<int> tati(202, -1);
vector<vector<int>> vecini(202);
queue<int> que;
int BFS()
{
fill(tati.begin(), tati.end(), -1);
tati[nod_start] = 0;
fill(temp_flow.begin(), temp_flow.end(), 0);
int current;
//clear the que
while (!que.empty())
{
que.pop();
}
que.push(nod_start);
// sa nu fie 1000 prea mic
temp_flow[nod_start] = 1000;
while(!que.empty())
{
current = que.front();
que.pop();
for(int vecin : vecini[current])
{
if(tati[vecin] == -1 && capacitate[current][vecin] - flow[current][vecin] > 0)
{
tati[vecin] = current;
temp_flow[vecin] = min(temp_flow[current],(capacitate[current][vecin] - flow[current][vecin]));
que.push(vecin);
if(vecin == nod_final)
return temp_flow[nod_final];
}
}
}
return 0;
}
int main(){
int n;
f >> n;
nod_final = 2 * n + 1;
for(int i = 1 ; i <= n; i++)
{
int out, in;
f >> out >> in;
capacitate[nod_start][i] = out;
capacitate[i + n][nod_final] = in;
vecini[nod_start].push_back(i);
vecini[n + i].push_back(nod_final);
// legam nodurile de la 1 la n cu cele de la n + 1 la 2n si le dam capacitatea 1
for(int j = n + 1; j <= n*2; j++)
{
//pentru a evita sa legam nodul de el insusi
if(j != i+n)
{
capacitate[i][j] = 1;
vecini[i].push_back(j);
vecini[j].push_back(i);
}
}
}
int flux_max = 0;
fill(flow.begin(), flow.end(), vector<int>(202, 0));
while(true) {
int flux = BFS();
if (flux == 0) {break;}
flux_max += flux;
int nod = nod_final;
//pusham flowul pe drumul gasit
while (nod != nod_start)
{
flow[ tati[nod] ][nod] += flux;
nod = tati[nod];
}
}
g << flux_max << endl;
for(int i = 1; i <= n; i++)
for(int j = 1 + n; j <= n * 2; j++)
if(flow[i][j])
g << i << ' ' << j - n << endl;
return 0;
}