Pagini recente » Cod sursa (job #2003729) | Cod sursa (job #1260690) | Cod sursa (job #807568) | Cod sursa (job #2403346) | Cod sursa (job #2959232)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("harta.in");
ofstream g ("harta.out");
vector<vector<int>> grade;
vector<vector<int>> graf(202, vector<int>(202, 0));
vector<int> parinte(202);
vector<bool> vizitat(202);
queue <int> coada;
// Pentru rezolvare vom folosi indicațiile din curs
// Anume, adăugăm un nod de start, un nod de terminal
// Formăm două mulțimi de noduri, prima mulțime o legăm la nodul de start
// A doua de nodul terminal
// Apoi, intre nodurile din cele multimi adaugam muchii, cu exceptia cand au acelasi indice (i == j)
// Adăugăm fluxul
// Apoi folosim aceeași metodă de rezolvarea ca la problema cu fluxul
// Complexitate (conform curs) O(m^2)
int n;
bool bfs(int n)
{
coada = queue <int> (); // golesc coada
fill(vizitat.begin(), vizitat.end(), false);
fill(parinte.begin(), parinte.end(), -1);
coada.push(0);
vizitat[0] = true;
while(!coada.empty())
{
int nod = coada.front();
coada.pop();
for(int i = 0; i <= n; i++)
{
if(graf[nod][i] > 0 && !vizitat[i])
{
coada.push(i);
vizitat[i] = true;
parinte[i] = nod;
if(i == n)
{
return true;
}
}
}
}
return false;
}
int FluxMaxim(int n)
{
int fluxMaxim = 0;
while(bfs(n))
{
for(int u = 1; u < n; u++)
{
if(graf[u][n] > 0 && vizitat[u])
{
vector<int> drum;
int capacitateMinima = INT_MAX;
drum.push_back(n);
drum.push_back(u);
int tata = parinte[u];
while(tata != -1)
{
drum.push_back(tata);
tata = parinte[tata];
}
for(int v = 1; v < drum.size(); v++)
capacitateMinima = min(capacitateMinima, graf[drum[v]][drum[v - 1]]);
fluxMaxim = fluxMaxim + capacitateMinima;
for(int v = 1; v < drum.size(); v++) {
graf[drum[v]][drum[v - 1]] -= capacitateMinima;
graf[drum[v - 1]][drum[v]] += capacitateMinima;
}
}
}
}
return fluxMaxim;
}
int main() {
f >> n;
grade.resize(n + 1);
for(int i = 1; i <= n; i++) {
int in, out;
f >> out >> in;
grade[i] = {out, in};
}
f.close();
// Precum în exemplul din curs, adăugăm un nod de start (0), și un
// un nod terminal (2 * n + 1) (2 * n pentru că avem cele două mulțimi)
// fluxul de la nodul de start la noduri va fi cel de pe prima coloană din
// fisierul de intrare, iar cel de la nodurile din a doua multime la terminal
// va fi cel de pe a doua coloana
for(int i = 1; i <= n; i++) {
graf[0][i] = grade[i][0];
graf[i + n][2 * n + 1] = grade[i][1];
}
// Acum adăugăm fluxul între nodurile din cele 2 multimi
// (conform cursului, acesta va fi 1)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
graf[i][n + j] = 1; //punem n + j ca sa fie din a doua multime
g << FluxMaxim(2 * n + 1) << "\n";
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= n * 2; j++)
if(graf[j][i] != 0)
g << i << " " << j - n << "\n";
return 0;
}