Pagini recente » Cod sursa (job #2442697) | Cod sursa (job #2329136) | Cod sursa (job #924313) | Cod sursa (job #140088) | Cod sursa (job #2961555)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <stack>
#include <unordered_map>
using namespace std;
// ifstream fin("input.txt");
// ofstream fout("output.txt");
ifstream fin("harta.in");
ofstream fout("harta.out");
/*
* Algotitm:
* - Se adauga un nou nod sursa si un nou nod destinatie (cu muchii care au costul egal cu gradul de intrare respectiv iesire)
* - Numarul de noduri se dubleaza si se pun in doua multimi distincte
* - Cele doua multimi se leaga intre ele prin muchii de cost 1 cu o conditie:
* - daca cele doua multimi sunt denumite X si Y, atunci va exista o muchie de la Xi la Yj daca i != j
* - Se aplica algoritmul lui Ford-Fulkerson pe graful rezultat
* - Muchiile saturate ne dau muchiile care fac parte din graful initial
*/
// --------------------------------- //
vector<int> tata;
vector<int> vizitat;
int a[300][300];
int intrare[300];
int iesire[300];
int n, m;
int s, d;
// --------------------------------- //
int bfs()
{
tata.clear();
tata.resize(2*n+2, 0);
vizitat.clear();
vizitat.resize(2*n+2, 0);
queue <int> q;
q.push(s);
vizitat[s] = 1;
tata[s] = -1;
while (!q.empty())
{
int nod = q.front();
q.pop();
if(nod == d)
return 1;
for (int i = 1; i <= 2 * n + 1; i++)
{
if (!vizitat[i] && a[nod][i] > 0)
{
q.push(i);
tata[i] = nod;
vizitat[i] = 1;
}
}
}
return 0;
}
int fordFulkerson()
{
int flux = 0;
int fluxCurent = 0;
while (bfs())
{
for(int i = 1; i <= n; i++)
{
if (vizitat[n + i] && a[n + i][2 * n + 1] > 0)
{
fluxCurent = INT_MAX;
tata[d] = n + i;
for(int nod = d; nod != s; nod = tata[nod])
fluxCurent = min(fluxCurent, a[tata[nod]][nod]);
if (fluxCurent == 0)
continue;
for (int nod = d; nod != s; nod = tata[nod])
{
a[tata[nod]][nod] -= fluxCurent;
a[nod][tata[nod]] += fluxCurent;
}
flux += fluxCurent;
}
}
}
return flux;
}
int main ()
{
fin >> n;
s = 0;
d = 2 * n + 1;
for(int i = 1; i <= n; i++)
{
// Citim datele de intrare
int x, y;
fin >> y >> x;
intrare[i] = x;
iesire[i] = y;
a[0][i] = y;
a[i + n][2 * n + 1] = x;
for(int j = 1; j <= n; j++)
{
if(i != j)
{
a[i][j + n] = 1;
}
}
}
fout << fordFulkerson() << endl;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(a[i][j + n] == 0 && i != j)
{
fout << i << " " << j << endl;
}
}
}
return 0;
}