Pagini recente » Cod sursa (job #1224971) | Cod sursa (job #3176724) | Cod sursa (job #624285) | Cod sursa (job #674311) | Cod sursa (job #2962371)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int N, sursa, dest,x,y;
int ad[201][201];
vector<bool> viz;
vector<int> tata;
int BFS()
{
tata.clear();
tata.resize(dest + 1, 0);
viz.clear();
viz.resize(dest + 1, false);
tata[sursa] = -1;
viz[sursa] = true;
queue<int> q;
q.push(sursa);
while (!q.empty())
{
int nod = q.front();
q.pop();
if (nod == dest) return 1; // nu flux maxim
for (int i = 1; i <= dest; i++)
if (!viz[i] && ad[nod][i] > 0) // cond nod nevizitat si capacitate nedepasita
{
tata[i] = nod;
viz[i] = true;
q.push(i);
}
}
// daca nu am ajuns in dest→ flux max
return 0;
}
int FordFulkerson()
{
long maxFlux = 0;
while (BFS()) //cat timp flux nu e maxim
{
// PENTRU FIECARE NOD, PARCURGEM DRUMUL GASIT
for (int i = 1; i <= N; i++)
{
if (viz[i + N] && ad[i + N][dest] > 0)
{
tata[dest] = i + N;
// determinam val min a gradelor
int flux = INT_MAX;
for (int nod = dest; nod != sursa; nod = tata[nod])
flux = min(flux, ad[tata[nod]][nod]);
// actualizam valorile gradelor nodurilor
for (int nod = dest; nod != sursa; nod = tata[nod])
{
ad[tata[nod]][nod] -= flux;
ad[nod][tata[nod]] += flux;
}
maxFlux += flux;
}
}
}
return maxFlux;
}
int main()
{
fin>>N;
// adaugam un nod sursa si unul destinatie
sursa = 0, dest = 2 * N + 1;
for (int i = 1; i <= N; i++)
{
fin>>y>>x; // y = grd_ext, x = grd_int
ad[sursa][i] = y; // adaugam muchie de la sursa; cost = grd_ext
ad[i + N][dest] = x; // adaugam muchie la dest; cost = grd_int
// adaugam muchiile intre noduri, capacitate = 1
for (int j = 1; j <= N; j++)
if (i != j) // conditie noduri distincte
ad[i][j + N] = 1;
}
fout<<FordFulkerson()<<'\n';
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (ad[i][j + N] == 0 && i != j) // cond capacitate si noduri distincte
fout<<i<<' '<<j<<'\n';
return 0;
}