fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. // find_maximum_matching nájde jedno maximálne párovanie v danom bipartitnom grafe
  7. // "A", "B" sú veľkosti ľavej a pravej partície ("počet chlapcov a dievčat")
  8. // "edge_list" je zoznam dvojíc ("ktoré dvojice sú ochotné spolu tancovať")
  9. // chlapcov aj dievčatá číslujeme od 0
  10.  
  11. vector< pair<int,int> >
  12. find_maximum_matching(
  13.         int A,
  14.         int B,
  15.         const vector< pair<int,int> > &edge_list)
  16. {
  17.  
  18.     // pre každé dievča si zapamätáme hrany do 'jej' chlapcov
  19.  
  20.     vector< vector<int> > BA;
  21.     BA.resize(B);
  22.     for (const auto &e : edge_list) BA[ e.second ].push_back( e.first );
  23.  
  24.     // pre každého chlapca si budeme updatovať jeho aktuálnu partnerku
  25.     // hodnota -1 znamená, že momentálne žiadnu nemá
  26.  
  27.     vector<int> match(A,-1);
  28.  
  29.     // na začiatku akoby máme všetkých chlapcov a žiadne dievčatá
  30.     // postupne po jednom pridávame dievčatá
  31.     // z pridaného dievčaťa vždy pustíme BFS ktorým hľadáme zlepšujúcu cestu
  32.  
  33.     for (int b=0; b<B; ++b) {
  34.  
  35.         // pribudlo dievča číslo b, ideme zistiť, či vieme zlepšiť riešenie
  36.  
  37.         // pre každého chlapca si pamätáme, či už bol počas BFS navštívený
  38.         // from[a] == -1 : ešte navštívený nebol
  39.         // from[a] == a  : bol navštívený priamo od dievčaťa b
  40.         // from[a] == a2 : bol navštívený tak, že sme od chlapca a2 išli
  41.         //                 k dievčaťu match[a2] a od nej ku chlapcovi a
  42.  
  43.         vector<int> from(A,-1);
  44.  
  45.         // všetkých chlapcov, ktorí sú ochotní tancovať s dievčaťom b,
  46.         // zaradíme do fronty na spracovanie a nastavíme im from[]
  47.  
  48.         queue<int> Q;
  49.         for (int a : BA[b]) { Q.push(a); from[a]=a; }
  50.  
  51.         // kým sa fronta nevyprázdni, prehľadávame
  52.  
  53.         while (!Q.empty()) {
  54.  
  55.             // vyberieme ďalšieho chlapca na spracovanie
  56.             // pozrieme sa, či má v aktuálnom párovaní partnerku
  57.  
  58.             int a = Q.front(); Q.pop();
  59.  
  60.             if (match[a] == -1) {
  61.  
  62.                 // tento chlapec nemá partnerku, našli sme teda zlepšujúcu cestu
  63.                 // upravíme podľa nej párovanie -- "o 1 poposúvame" partnerky
  64.  
  65.                 while (from[a] != a) { 
  66.  
  67.                     // aktuálny chlapec dostane ako partnerku dievča, z ktorého
  68.                     // sme doň prišli -- teda doterajšiu partnerku chlapca from[a]
  69.  
  70.                     match[a] = match[from[a]]; 
  71.  
  72.                     // presunieme sa na toho chlapca a úvahu opakujeme, až kým
  73.                     // neprejdeme celú cestu
  74.  
  75.                     a = from[a]; 
  76.                 }
  77.  
  78.                 // na konci zlepšujúcej cesty ešte poslednému chlapcovi dáme ako
  79.                 // novú partnerku práve pribudnuvšie dievča b
  80.  
  81.                 match[a] = b;
  82.  
  83.                 // a celé prehľadávanie ukončíme
  84.  
  85.                 break;
  86.  
  87.             } else {
  88.  
  89.                 // práve spracúvaný chlapec partnerku má, pozrieme sa na ňu
  90.                 // všetkých ostatných chlapcov, ktorí sú s ňou ochotní tancovať
  91.                 //     a ešte neboli objavení prehľadávaním, zaradíme do fronty
  92.                 //     na spracovanie
  93.  
  94.                 for (int x : BA[match[a]]) if (from[x]==-1) { Q.push(x); from[x]=a; }
  95.             }
  96.         }
  97.     }
  98.  
  99.     // v tomto okamihu máme zostrojené a v poli match[] zapamätané jedno maximálne
  100.     // párovanie, prerobíme ho na zoznam hrán a ten vrátime na výstup
  101.  
  102.     vector< pair<int,int> > result;
  103.     for (int a=0; a<A; ++a) if (match[a] != -1) result.push_back( { a, match[a] } );
  104.     return result;
  105. }
  106.  
  107. int main() {
  108.     // malý test: 3 chlapci, 3 dievčatá, chlapec 0 tancuje s hociktorou, 
  109.     // dievča 0 tancuje s hociktorým
  110.     // optimálne párovanie je tvorené dvoma dvojicami, napr. 0-2 a 1-0.
  111.  
  112.     vector< pair<int,int> > edge_list = { {0,0}, {0,1}, {0,2}, {1,0}, {2,0} };
  113.     cout << find_maximum_matching(3, 3, edge_list).size() << endl;
  114. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/KB23jk
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!