Pagini recente » Cod sursa (job #1321444) | Cod sursa (job #2532714) | Cod sursa (job #1170166) | Cod sursa (job #455564) | Cod sursa (job #3193553)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int MaxN = 205;
int nrOr, nrDr, srs, dest, flow[MaxN][MaxN], cap[MaxN][MaxN] , from[MaxN];
bool bfs()
{
queue<int> q;
vector<bool> viz(MaxN, false);
q.push(srs);
viz[srs] = true;
while (!q.empty() && !viz[dest])
{
int nod = q.front();
for (int vec = 1; vec <= dest; ++vec)
if (vec != nod && !viz[vec] && flow[nod][vec] < cap[nod][vec])
{
from[vec] = nod;
viz[vec] = true;
q.push(vec);
}
q.pop();
}
return viz[dest];
}
int main()
{
f >> nrOr;
srs = 2 * nrOr + 3;
dest = 2 * nrOr + 2;
for (int i = 1; i <= nrOr; ++i)
for (int j = i + 1; j <= nrOr; ++j)
{
cap[2 * i][2 * j + 1] = cap[2 * j][2 * i + 1] = 1;
}
for (int i = 1; i <= nrOr; ++i)
{
int a, b;
f >> a >> b;
nrDr += a;
cap[2 * i + 1][dest] = b;
cap[srs][2 * i] = a;
}
// Aplicarea algoritmului Edmonds-Karp pt fluxul maxim
while (bfs())
{
for (int i = 1; i <= srs; ++i)
if (from[i] && flow[i][dest] < cap[i][dest])
{
from[dest] = i;
int node = dest, mini = 10000;
while (from[node])
{
mini = min(mini, cap[from[node]][node] - flow[from[node]][node]);
node = from[node];
}
node = dest;
while (from[node])
{
flow[from[node]][node] += mini;
flow[node][from[node]] -= mini;
node = from[node];
}
}
}
g << nrDr << '\n';
for (int i = 1; i < dest; ++i)
for (int j = 1; j < dest; ++j)
if (flow[i][j] > 0)
g << i/2 << ' ' << j/2 << '\n';
return 0;
}