Pagini recente » Cod sursa (job #419897) | Cod sursa (job #2329418) | Cod sursa (job #1607147) | Cod sursa (job #150968) | Cod sursa (job #2965865)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, sursa, destinatie;
vector<vector<int>> graf;
vector<int> parinte;
int capacitate[201][201];
bool bfs()
{
vector<int> vizitat(destinatie);
queue<int> q;
q.push(sursa);
vizitat[sursa] = 1;
parinte[sursa] = -1;
while(!q.empty())
{
int u = q.front();
q.pop();
for (auto v:graf[u])
{
if (vizitat[v] == 0 && capacitate[u][v] != 0)
{
parinte[v] = u;
if(v == destinatie)
return true;
vizitat[v] = 1;
q.push(v);
}
}
}
return false;
}
int EdmondsKarp()
{
int fluxMax = 0;
//cat inca exista un drum neviz
while(bfs())
{
int nod1, nod2;
nod2 = destinatie;
int capDrum = INT_MAX;
//parcurgere drum pentru a cauta capacitatea minima
while(nod2 != sursa)
{
nod1 = parinte[nod2];
if(capacitate[nod1][nod2] < capDrum)
capDrum=capacitate[nod1][nod2];
nod2 = parinte[nod2];
}
nod2 = destinatie;
//parcurgere drum pt a actualiza capacitatile muchiilor
while(nod2 != sursa)
{
nod1 = parinte[nod2];
capacitate[nod1][nod2] -= capDrum; // cap muchiei din graful initial scade
capacitate[nod2][nod1] += capDrum; // cap muchiei inverse creste
nod2=parinte[nod2];
}
fluxMax = fluxMax + capDrum;
}
return fluxMax;
}
void afisare()
{
fout << EdmondsKarp() << endl;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (capacitate[j + n][i] == 1)
fout << i << " " << j << endl;
}
int main()
{
fin >> n;
sursa = 0;
destinatie = 2 * n + 1;
parinte.resize(2 * n + 1);
graf.resize(201);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i != j)
{
graf[i].push_back(j + n);
graf[j + n].push_back(i);
capacitate[i][j + n] = 1;
}
}
int a, b;
for (int i = 1; i <= n; i++)
{
fin >> a >> b;
graf[sursa].push_back(i);
graf[i].push_back(sursa);
capacitate[sursa][i] = a;
graf[destinatie].push_back(i + n);
graf[i + n].push_back(destinatie);
capacitate[i + n][destinatie] = b;
}
afisare();
return 0;
}