fork(1) download
copy 
  1. /*input
  2. 4
  3. 1 4 6 2
  4. 5
  5. 5 1 5 7 9
  6. */
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <queue>
  11. #include <climits>
  12. using namespace std;
  13. #define pb push_back
  14. #define sz 100001
  15.  
  16. int boysSkillz[sz], girlsSkillz[sz];
  17.  
  18. //Maximal Matching begins
  19. vector<int> adj[sz];
  20. int pairU [sz], pairV[sz], dist[sz];
  21.  
  22. bool HK_Bfs(int m)
  23. {
  24.     queue<int> Q;
  25.     for (int u=1; u<=m; u++)
  26.     {
  27.         if (pairU[u]==0)
  28.         {
  29.             dist[u] = 0;
  30.             Q.push(u);
  31.         }
  32.         else
  33.             dist[u] = INT_MAX;
  34.     }
  35.     dist[0] = INT_MAX;
  36.     while (!Q.empty())
  37.     {
  38.         int u = Q.front();
  39.         Q.pop();
  40.         if (dist[u] < dist[0])
  41.             for (int v:adj[u])
  42.                 if (dist[pairV[v]] == INT_MAX)
  43.                 {
  44.                     dist[pairV[v]] = dist[u]+1;
  45.                     Q.push(pairV[v]);
  46.                 }
  47.     }
  48.     return (dist[0] != INT_MAX);
  49. }
  50.  
  51. bool HK_Dfs(int u)
  52. {
  53.     if (u != 0)
  54.     {
  55.         for (int v: adj[u])
  56.             if (dist[pairV[v]] == dist[u]+1 && HK_Dfs(pairV[v]))
  57.             {
  58.                 pairV[v] = u;
  59.                 pairU[u] = v;
  60.                 return true;
  61.             }
  62.         dist[u] = INT_MAX;
  63.         return false;
  64.     }
  65.     return true;
  66. }
  67.  
  68. int HopcroftKarp(int m, int n)
  69. {
  70.     for (int u=0; u<m; u++)
  71.         pairU[u] = 0;
  72.     for (int v=0; v<n; v++)
  73.         pairV[v] = 0;
  74.     int maxMatching = 0;
  75.  
  76.     while (HK_Bfs(m))
  77.         for (int u=1; u<=m; u++)
  78.             if (pairU[u]==0 && HK_Dfs(u))
  79.                 maxMatching++;
  80.     return maxMatching;
  81. }
  82. //Maximal Matching ends
  83.  
  84. int main()
  85. {
  86. 	int n, m;
  87. 	cin>>n;
  88. 	for(int i=1;i<=n;i++)
  89. 		cin>>boysSkillz[i];
  90. 	cin>>m;
  91. 	for(int i=1;i<=m;i++)
  92. 		cin>>girlsSkillz[i];
  93. 	for(int i=1;i<=n;i++) //Building graph according to logic mentioned
  94. 		for(int j=1;j<=m;j++)
  95. 			if(abs(boysSkillz[i]-girlsSkillz[j])<=1)
  96. 			{
  97. 				adj[i].pb(j);
  98. 				adj[j].pb(i);
  99. 			}
  100. 	cout<<HopcroftKarp(n,m);
  101. 	return 0;
  102. }
Success #stdin #stdout 0s 6544KB
comments (?)
stdin
copy 
4
1 4 6 2
5
5 1 5 7 9
stdout
copy 
4
https://ideone.com/WOcE8I
language:
C++14 (gcc 8.3)
created:
10 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!