Advertisement
Guest User

Untitled

a guest
Jul 24th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int>sasiedzi[200+5];
  6. vector<int>sasiedzi_gornych[200+5];
  7. bool jest_dolny[200+5];
  8. bool odw[200+5];
  9. int odw_nr[200+5];
  10. int partner[200+5];
  11.  
  12. int n;
  13. int nr = 1;
  14. int wynik = 0;
  15.  
  16. void DFS_odw(int w)
  17. {
  18.     odw[w] = true;
  19.     for(int i=0; i<sasiedzi[w].size(); i++)
  20.         if(odw[sasiedzi[w][i]] == false)
  21.             DFS_odw(sasiedzi[w][i]);
  22. }
  23.  
  24. bool Match(int w)
  25. {
  26.  //   cout<<endl;
  27.    // cout<<"WYWOLANO MATCH DLA W: "<<w<<endl;
  28.     odw_nr[w] = nr;
  29.  
  30.     ///DLA KAZDEJ WOLNEJ
  31.     int ile_opcji = sasiedzi_gornych[w].size();
  32.  
  33.     for(int i=0; i<ile_opcji; i++)
  34.     {
  35.         int akt_opcja = sasiedzi_gornych[w][i];
  36.      //   cout<<"AKT OPCJA: "<<akt_opcja<<endl;
  37.  
  38.  
  39.         if(partner[akt_opcja] == 0)
  40.         {
  41.             partner[akt_opcja] = w;
  42.        //     cout<<"wolna, teraz "<<akt_opcja<<"ma partnera: "<<w<<endl;
  43.             return 1;
  44.         }
  45.     }
  46.  
  47.     for(int i=0; i<ile_opcji; i++)
  48.     {
  49.         int akt_opcja = sasiedzi_gornych[w][i];
  50.         int part_opcji = partner[akt_opcja];
  51.         if(odw_nr[part_opcji] != nr && Match(part_opcji) == 1)
  52.         {partner[akt_opcja] = w; return 1;}
  53.  
  54.     }
  55.  
  56.     return 0;
  57.  
  58. }
  59.  
  60. int main()
  61. {
  62.     cin>>n;
  63.  
  64.     int t1;
  65.     int t2;
  66.     for(int i=1; i<n; i++)
  67.     {
  68.         cin>>t1;
  69.         for(int j=1; j<=t1; j++)
  70.         {
  71.             cin>>t2;
  72.             sasiedzi[i].push_back(t2);
  73.  
  74.             if(t2 == n)
  75.                 jest_dolny[i] = true;
  76.         }
  77.     }
  78.  
  79.     bool istnieje_polaczenie_1_do_n = false;
  80.     for(int i=0; i<sasiedzi[1].size(); i++)
  81.         if(sasiedzi[1][i] == n)
  82.             {istnieje_polaczenie_1_do_n = true; sasiedzi[1].erase(sasiedzi[1].begin() + i); break;}
  83.  
  84.      /*       cout<<"SASIEDZI"<<endl;
  85.      for(int i=1; i<=n; i++)
  86.     {
  87.         cout<<i<<": "<<sasiedzi[i].size()<<endl;
  88.         for(int j=0; j<sasiedzi[i].size(); j++)
  89.             cout<<sasiedzi[i][j]<<"  ";
  90.         cout<<endl;
  91.  
  92.     }*/
  93.  
  94.  
  95.     ///DLA KAZDEGO GORENEGO
  96.     for(int i=0; i<sasiedzi[1].size(); i++)
  97.     {
  98.        // cout<<"DLA GORNEGO: "<<sasiedzi[1][i]<<endl;
  99.         for(int j=0; j<=n; j++)
  100.             odw[j] = false;
  101.  
  102.         DFS_odw(sasiedzi[1][i]);
  103.  
  104.         for(int j=1; j<=n; j++)
  105.         {
  106.             //cout<<"j: "<<j<<" odw[j]: "<<odw[j]<<" jest_dolny[j]:  "<<jest_dolny[j]<<endl;
  107.             if(odw[j] == 1 && jest_dolny[j] == 1)
  108.                 {
  109.                    // cout<<"dodaje dla: "<<sasiedzi[1][i]<<" wartosc: "<<j<<endl;
  110.                     sasiedzi_gornych[sasiedzi[1][i]].push_back(j);
  111.                 }
  112.         }
  113.        // cout<<endl;
  114.  
  115.     }
  116.  
  117.     /*for(int i=1; i<=n; i++)
  118.     {
  119.         cout<<i<<": "<<sasiedzi_gornych[i].size()<<endl;
  120.         for(int j=0; j<sasiedzi_gornych[i].size(); j++)
  121.             cout<<sasiedzi_gornych[i][j]<<"  ";
  122.         cout<<endl;
  123.  
  124.     }*/
  125.     ///DOTAD OK
  126.  
  127.  
  128.     for(int i=0; i<sasiedzi[1].size(); i++)
  129.     {
  130.         wynik += int(Match(sasiedzi[1][i]));
  131.         nr++;
  132.     }
  133.  
  134.     cout<<wynik+int(istnieje_polaczenie_1_do_n);
  135.  
  136.     return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement