Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <cstring> using namespace std; const int MAX_N = 101; //L go oznachuva brojot na elementi vo levoto mnozhestvo //R go oznachuva brojot na elementi vo desnoto mnozhestvo int L, R; vector<int> G[MAX_N]; //left_of[i] oznachuva koj element od levoto mnozhestvo e //povrzan so i-tiot element od desnoto mnozhestvo //na primer, left_of[3] = 0 znachi deka elementot 3 od desnoto mnozhestvo //e povrzan so elementot 0 od levoto mnozhestvo int left_of[MAX_N]; //right_of[i] oznachuva koj element od desnoto mnozhestvo e //povrzan so i-tiot element od levoto mnozhestvo //na primer, right_of[0] = 3 znachi deka elementot 0 od levoto mnozhestvo //e povrzan so elementot 3 od desnoto mnozhestvo int right_of[MAX_N]; //pomoshna niza, koja se koristi za da znaeme koga da zapreme so rekurzijata int seen[MAX_N]; //algoritamot pochnuva od funkcijata bipartite_matching(), //pa zapochete i vie so chitanje od tamu bool find_match(int index) { //index pokazhuva na elementi od levoto mnozhestvo if (seen[index]) { return false; } seen[index] = 1; //obidi se da najdesh teme od desnoto mnozhestvo koe nema povrzuvanje for (int next : G[index]) { if (left_of[next] == -1) { //najdovme slobodno teme left_of[next] = index; right_of[index] = next; return true; } } //ne pronajdovme nishto, pa obidi se za premestish teme od desnoto mnozhestvo for (int next : G[index]) { int current_connection = left_of[next]; if (find_match(current_connection)) { //ok, "next" e sega slobodno, povrzi go left_of[next] = index; right_of[index] = next; return true; } } //ne pronajdovme spojuvanje za "index" return false; } int bipartite_matching() { //koristime -1 za oznachuvanje deka ne postoi vrska memset(left_of, -1, sizeof(left_of)); memset(right_of, -1, sizeof(right_of)); int matched = 0; for (int i=0; i<L; i++) { //postavi/resetiraj go "seen" so nuli //"seen" se koristi pri rekurzijata, //za da znaeme koga da zapreme memset(seen, 0, sizeof(seen)); if (find_match(i)) { matched++; } } return matched; } int main() { L = 5; R = 4; //napravi go pochetniot graf (na primer, koj rabotnik //mozhe da raboti na koe rabotno mesto) //(indeksite pochnuvaat od 0) G[0].push_back(0); //elementot 0 od prvoto mnozhestvo do 0 od vtoroto G[0].push_back(1); G[1].push_back(1); G[3].push_back(3); G[4].push_back(3); int matched = bipartite_matching(); cout << "Matched " << matched << " elements." << endl; return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!