Pagini recente » Cod sursa (job #837836) | Cod sursa (job #403398) | Cod sursa (job #1649163) | Cod sursa (job #653731) | Cod sursa (job #2962031)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int N, SURSA, DESTINATIE;
// MATRICE DE ADIACENTA
int m_a[301][301];
// VECTOR CARE DETERMINA DACA UN NOD A FOST SAU NU VIZITAT
vector<bool> vizitat;
// VECTOR DE TATI
vector<int> v_p;
int BFS()
{
v_p.clear();
v_p.resize(DESTINATIE + 1, 0);
vizitat.clear();
vizitat.resize(DESTINATIE + 1, false);
v_p[SURSA] = -1;
vizitat[SURSA] = true;
// COADA PENTRU PARCURGEREA GRAFULUI
queue <int> q;
q.push(SURSA);
while (!q.empty())
{
int n_curent = q.front();
q.pop();
if (n_curent == DESTINATIE) return 1;
for (int i = 1; i <= DESTINATIE; i++)
if (!vizitat[i] && m_a[n_curent][i] > 0)
{
q.push(i);
v_p[i] = n_curent;
vizitat[i] = true;
}
}
return 0;
}
int FORDFULKERSON()
{
int m_flux = 0;
while (BFS())
{
for(int i = 1; i <= N; i++)
{
if (vizitat[N + i] && m_a[N + i][DESTINATIE] > 0)
{
v_p[DESTINATIE] = N + i;
int flux = INT_MAX;
for(int nod = DESTINATIE; nod != SURSA; nod = v_p[nod])
flux = min(flux, m_a[v_p[nod]][nod]);
for (int nod = DESTINATIE; nod != SURSA; nod = v_p[nod])
{
m_a[v_p[nod]][nod] -= flux;
m_a[nod][v_p[nod]] += flux;
}
m_flux += flux;
}
}
}
return m_flux;
}
int main ()
{
fin>>N;
SURSA = 0;
DESTINATIE = 2 * N + 1;
for(int i = 1; i <= N; i++)
{
int x, y;
fin >> y >> x;
m_a[SURSA][i] = y;
m_a[i + N][DESTINATIE] = x;
for(int j = 1; j <= N; j++)
{
if(i != j)
{
m_a[i][j + N] = 1;
}
}
}
fout<<FORDFULKERSON()<<endl;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
if(m_a[i][j + N] == 0 && i != j)
{
fout << i << " " << j << endl;
}
}
}
return 0;
}