fork(1) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<limits>
  13. #include<climits>
  14. #include<cmath>
  15. #include<functional>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<fstream>
  19.  
  20. using namespace std;
  21.  
  22. struct data
  23. {
  24.     int height,age,indicator;
  25. };
  26.  
  27. const int MAX = 64;
  28.  
  29. data men_data[MAX];
  30. data women_data[MAX];
  31.  
  32. int men_match[MAX],women_match[MAX];
  33. bool used[MAX];
  34. vector <int> preferences[MAX];
  35.  
  36. int n,m;
  37.  
  38. int alternating_path[256],sz;
  39.  
  40. void input()
  41. {
  42.     int i,j;
  43.     memset(men_match,0,sizeof(men_match));
  44.     memset(women_match,0,sizeof(women_match));
  45.     for(i=0;i<MAX;i++)
  46.         preferences[i].clear();
  47.     scanf("%d %d", &n, &m);
  48.     for(i=1;i<=n;i++)
  49.     {
  50.         scanf("%d %d %d", &men_data[i].height, &men_data[i].age, &men_data[i].indicator);
  51.     }
  52.     for(i=1;i<=m;i++)
  53.     {
  54.         scanf("%d %d %d", &women_data[i].height, &women_data[i].age, &women_data[i].indicator);
  55.     }
  56.     for(i=1;i<=n;i++)
  57.     {
  58.         for(j=1;j<=m;j++)
  59.         {
  60.             if(abs(men_data[i].height-women_data[j].height)<=12)
  61.                 if(abs(men_data[i].age-women_data[j].age)<=5)
  62.                     if(men_data[i].indicator==women_data[j].indicator)
  63.                         preferences[i].push_back(j);
  64.         }
  65.     }
  66. }
  67. bool DFS(int curr, bool type)
  68. {
  69.     alternating_path[sz++]=curr;
  70.     if(type==0)
  71.     {
  72.         for(int i=0;i<preferences[curr].size();i++)
  73.         {
  74.             if(!used[preferences[curr][i]] && women_match[preferences[curr][i]]!=curr)
  75.             {
  76.                 used[preferences[curr][i]]=true;
  77.                 if(DFS(preferences[curr][i],1))
  78.                     return true;
  79.                 used[preferences[curr][i]]=false;
  80.             }
  81.         }
  82.     }
  83.     else
  84.     {
  85.         if(women_match[curr]==0)
  86.             return true;
  87.         if(DFS(women_match[curr],0))
  88.             return true;
  89.     }
  90.     sz--;
  91.     return false;
  92. }
  93. void solve()
  94. {
  95.     bool path_found;
  96.     int i;
  97.     int ans=0;
  98.     while(true)
  99.     {
  100.         sz=0;
  101.         path_found=false;
  102.         for(i=1;i<=n;i++)
  103.         {
  104.             memset(used,0,sizeof(used));
  105.             if(men_match[i]==0)
  106.             {
  107.                 if(DFS(i,0))
  108.                 {
  109.                     path_found=true;
  110.                     break;
  111.                 }
  112.             }
  113.         }
  114.         if(path_found==false)
  115.             break;
  116.         for(i=0;i<sz;i+=2)
  117.         {
  118.             men_match[alternating_path[i]]=alternating_path[i+1];
  119.             women_match[alternating_path[i+1]]=alternating_path[i];
  120.         }
  121.     }
  122.     for(i=1;i<=n;i++)
  123.         ans+=(men_match[i]>0);
  124.     printf("%d\n", ans);
  125. }
  126. int main()
  127. {
  128.     int i,t;
  129.     scanf("%d", &t);
  130.     for(i=1;i<=t;i++)
  131.     {
  132.         input();
  133.         printf("Case %d: ", i);
  134.         solve();
  135.     }
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0s 3148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lGgTXz
language:
C++ (gcc 8.3)
created:
9 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!