Pagini recente » Cod sursa (job #2999285) | Cod sursa (job #262565) | Cod sursa (job #2298832) | Cod sursa (job #566933) | Cod sursa (job #2961880)
#include <fstream>
#include <vector>
#include <queue>
#define INT_MAX 2147483647;
using namespace std;
//3.
int n, m, maxFlow, start, final;
vector<vector<int>> rez;
vector<int> anc, gradExt, gradInt;
vector<bool> viz;
//parcurgerea bfs care gaseste lanturi de la start la final:
bool bfs() {
queue<int> q;
anc.clear();
anc.resize(2*n + 2, -1);
viz.clear();
viz.resize(2*n + 2, false);
q.push(start);
viz[start] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
if (curr == final)
continue;
for (int i = 1; i <= 2 * n + 1; i++) {
if (!viz[i] && rez[curr][i] > 0) {
anc[i] = curr;
q.push(i);
viz[i] = true;
}
}
}
return viz[final];
}
//algoritmul edmonds-karp:
void edmondsKarp() {
//cat timp mai exista lanturi care pot fi parcurse de la start la final, continuam sa le parcurgem adaugand flux:
while (bfs()) {
//pentru toate drumurile care au dus la final:
for (int i = n+1; i <= 2*n; i++)
{
if (!(viz[i] && rez[i][final] != 0))
continue;
//caut bottleneck-ul, reprezentand noul flux:
int aux = i;
int min = rez[aux][final];
while (aux != start) {
if (rez[anc[aux]][aux] < min)
min = rez[anc[aux]][aux];
aux = anc[aux];
}
//updatez matricea reziduala, adaugand noul flux:
aux = i;
rez[aux][final] -= min;
rez[final][aux] += min;
while (aux != start) {
rez[anc[aux]][aux] -= min;
rez[aux][anc[aux]] += min;
aux = anc[aux];
}
maxFlow += min;
}
}
}
//citirea datelor: trebuie sa modelam datele sub forma unui graf orientat pe care calcularea fluxului maxim va determina arcele de pe harta, astfel
//adaugam doua noduri auxiliare, nodul de start si nodul de final, iar restul nodurilor, cele care reprezinta puncte pe harta, se vor dubla, formand doua multimi
//in care fiecare nod din prima multime va fi unit de toate cele din a doua multime, mai putin de dublura lui
void citire() {
ifstream fin("harta.in");
int gInt, gExt;
fin >> n;
start = 0;
final = 2 * n + 1;
rez.resize(2*n + 2, vector<int>(2*n + 2, 0));
gradInt.resize(n + 1);
gradExt.resize(n + 1);
for (int i = 1; i <= n; i++) {
fin >> gradExt[i] >> gradInt[i];
rez[start][i] = gradExt[i];
rez[i + n][final] = gradInt[i];
for (int j = 1; j <= n; j++)
{
if (i != j)
{
rez[i][j + n] = 1;
}
}
}
fin.close();
}
void afisare() {
ofstream fout("harta.out");
fout << maxFlow << "\n";
for (int i = 1; i <= n; i++)
{
for (int j = n + 1; j <= n * 2; j++)
{
if (rez[i][j] == 0 && i != j - n)
{
fout << i << " " << j - n << "\n";
}
}
}
fout.close();
}
int main()
{
citire();
edmondsKarp();
afisare();
return 0;
}