Pagini recente » Cod sursa (job #3220054) | Cod sursa (job #1629312) | Cod sursa (job #918310) | Cod sursa (job #2541532) | Cod sursa (job #2963991)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
typedef struct
{
int start;
int finish;
} legatura;
typedef struct
{
int flow;
int capacitate;
} dual;
typedef struct
{
int val;
bool out;
} vecin;
int n1,n2,m;
int nr_noduri,n;
vector<vector<vecin>> lista_adiacenta;
vector<int> tata;
dual matrice[1001][1001];
vector<int> taietura;
vector<legatura> solutie;
vector<int> vizitat_global;
void citire()
{
f >> n1 >> n2 >> m;
nr_noduri = n1+n2;
n = nr_noduri+1;
lista_adiacenta.reserve(n+1);
vizitat_global.resize(n+1,false);
int i;
for(i=0;i<=n;i++)
{
vector<vecin> aux;
lista_adiacenta.push_back(aux);
}
for(i=1;i<=n1;i++)
{
matrice[0][i].capacitate = 1;
matrice[0][i].flow = 0;
lista_adiacenta[0].push_back({i,true});
lista_adiacenta[i].push_back({0,false});
}
for(i=1;i<=n2;i++)
{
int aux = n1+i;
matrice[aux][n].capacitate = 1;
matrice[aux][n].flow = 0;
lista_adiacenta[aux].push_back({n,true});
lista_adiacenta[n].push_back({aux,false});
}
int x,y,poz2;
for(i=1;i<=m;i++)
{
f>>x>>y;
poz2 = n1 + y;
//cout << "afisare: " << x<< " -> " << poz2 << endl;
matrice[x][poz2].capacitate = 1;
matrice[x][poz2].flow = 0;
matrice[poz2][x].capacitate = 1;
matrice[poz2][x].flow = 0;
lista_adiacenta[x].push_back({poz2,true});
lista_adiacenta[poz2].push_back({x,false});
}
}
bool BFS()
{
taietura.clear();
taietura.reserve(n);
taietura.push_back(1);
//cout << "\n\n\nBFS\n\n\n";
queue<int> coada;
tata.clear();
tata.resize(n+1, 0);
vector<bool> vizitat;
vizitat.resize(n+1, false);
coada.push(0);
vizitat[0] = true;
int curent;
int destinatie;
int rezidual;
while(!coada.empty())
{
curent = coada.front();
coada.pop();
for(auto &it : lista_adiacenta[curent])
{
destinatie = it.val;
if(!vizitat[destinatie] && !vizitat_global[destinatie])
{
if(it.out)
{
// daca este nod care iese din curent
rezidual = matrice[curent][destinatie].capacitate - matrice[curent][destinatie].flow;
if(rezidual > 0)
{
tata[destinatie] = curent;
vizitat[destinatie] = true;
coada.push(destinatie);
taietura.push_back(destinatie);
//cout << curent << " -> " << destinatie << " = " << rezidual << endl;
if(destinatie == n)
{
return true;
}
}
}
else
{
// daca este nod care intra in curent
rezidual = matrice[destinatie][curent].flow;
if(rezidual > 0)
{
tata[destinatie] = -curent;
vizitat[destinatie] = true;
coada.push(destinatie);
taietura.push_back(destinatie);
//cout << destinatie << " ====> " << curent << " = " << rezidual << endl;
if(destinatie == n)
return true;
}
}
}
}
}
return false;
}
void revizuieste()
{
//cout << "\n\n\n\nREVIZUIRE\n\n\n";
int curent = n;
int t = tata[n];
int rezidual;
int minim = 999999;
// variabile pt adaugare legaturi cuplaj
int sfarsit,inceput;
sfarsit = tata[n];
if(sfarsit < 0)
sfarsit = -sfarsit;
inceput = tata[sfarsit];
if(inceput < 0)
inceput = -inceput;
//cout << " inceput : " << inceput << " --- sfarsit : " << sfarsit << endl;
sfarsit -= n1;
solutie.push_back({inceput,sfarsit});
while(curent!=0)
{
if(t < 0)
{
rezidual = matrice[curent][-t].flow;
t = -t;
//if(rezidual == 0)
//cout << -t << " -> " << curent << endl;
}
else
rezidual = matrice[t][curent].capacitate - matrice[t][curent].flow;
//cout << t << " -> " << curent << endl;
minim = min(rezidual,minim);
curent = t;
if(curent != 0)
t = tata[curent];
}
curent = n;
t = tata[n];
while(curent!=0)
{
if(t < 0)
{
t = -t;
matrice[curent][t].flow -= minim;
}
else
matrice[t][curent].flow += minim;
curent = t;
if(curent!=0)
t = tata[curent];
}
}
int main()
{
citire();
while(BFS())
revizuieste();
/*
cout << "TAIETURA MINIMA:\n";
for(int& nod : taietura)
cout << nod << " ";
cout << endl << endl << endl;
*/
g << solutie.size() << endl;
for(auto &leg : solutie)
g << leg.start << " " << leg.finish << endl;
}