Pagini recente » Cod sursa (job #652855) | Cod sursa (job #2718839) | Cod sursa (job #910025) | Cod sursa (job #357679) | Cod sursa (job #3189553)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
// Nmax = 202 (s = 0, 100 noduri originale, 100 copii, t = 201)
int capacitate[205][205], matriceFlux[205][205];
vector <int> listaAdiacenta[205];
int tati[205];
int N;
int nrMuchii;
void afiseazaListaAdiacenta(int n)
{
for (int i = 0; i <= n; i++)
{
cout << "Nodul " << i << " adiacent cu: ";
for (int j = 0; j < listaAdiacenta[i].size(); j++)
{
cout << listaAdiacenta[i][j] << " ";
}
cout << endl;
}
}
void afiseazaCapacitate()
{
int n = 2 * N + 1;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
cout << capacitate[i][j] << " ";
}
cout << endl;
}
}
void afiseazaMatriceFlux()
{
int n = 2 * N + 1;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
cout << matriceFlux[i][j] << " ";
}
cout << endl;
}
}
int bfs(int start, int stop)
{
vector <int> fluxIesire(205, 0); // fluxul care iese din fiecare nod la pasul curent
for (int i = 0; i <= 2 * N + 1; i++)
{
tati[i] = -1;
}
queue<int> coada;
coada.push(start);
tati[start] = -2;
fluxIesire[start] = 999999999;
while (!coada.empty())
{
int nod = coada.front();
coada.pop();
// luam toti vecinii
for (int vecin : listaAdiacenta[nod])
{
// daca n am ajuns pe un vecin
if (tati[vecin] == -1)
{
// daca putem sa bagam flux in el
if (capacitate[nod][vecin] - matriceFlux[nod][vecin] > 0)
{
tati[vecin] = nod;
fluxIesire[vecin] = min(fluxIesire[nod], capacitate[nod][vecin] - matriceFlux[nod][vecin]);
if (vecin == stop)
{
return fluxIesire[stop];
}
coada.push(vecin);
}
}
}
}
}
int edmondsKarp(int start, int stop)
{
int fluxMax = 0;
while (fluxMax != nrMuchii)
{
// cu bfs gasim fluxul -> drumul cel mai scurt de ameliorare (augumenting path)
int flux = bfs(start, stop);
// daca nu mai avem augumenting path e pa pa
if (!flux)
{
break;
}
// crestem fluxul maxim
fluxMax += flux;
// refacem drumul fluxului si actualizam matricea de flux
// nod = nodul pe care suntem in momentul ala
int nod = stop;
while (nod != start)
{
int anterior = tati[nod];
matriceFlux[anterior][nod] += flux;
matriceFlux[nod][anterior] -= flux;
nod = anterior;
}
}
return fluxMax;
}
int main()
{
int s, t;
fin >> N;
s = 0;
t = N * 2 + 1;
// la citire: pt fiecare nod facem o copie (d asta e matricea "dubla" ca dimensiune)
// facem legaturi sursa -> original cu capacitate = grad extern pt toate nodurile
// si copie -> sink (final) cu capacitate = grad intern pt toate nodurile
// apoi pt fiecare pereche (i j) cu i != j facem original i -> copie j cu capacitate = 1
// si copie j -> original i cu capacitate = 1
for (int i = 1; i <= N; i++)
{
int exterior, interior;
fin >> exterior >> interior;
nrMuchii += exterior;
capacitate[s][i] = exterior;
capacitate[i + N][t] = interior;
listaAdiacenta[s].push_back(i);
listaAdiacenta[i + N].push_back(t);
for (int j = N + 1; j <= 2 * N; j++)
{
if (i % N != j % N)
{
capacitate[i][j] = 1;
listaAdiacenta[i].push_back(j);
listaAdiacenta[j].push_back(i);
}
}
}
fout << edmondsKarp(s, t) << endl;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (matriceFlux[i][j + N] > 0)
{
fout << i << " " << j << endl;
}
}
}
return 0;
}