fork download
copy 
  1. /// Hopcroft-Karp+Konig by muoii
  2.  
  3. /// vn.spoj.com/problems/NKBM/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define tag "spoj"
  7. #define maxn 10007
  8. #define oo 2000000007
  9. #define meset(a,x) memset(a,x,sizeof(a))
  10. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  11. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  12. int m,n,p;
  13. int d[maxn],mx[maxn],my[maxn];
  14. vector<int> adx[maxn],ady[maxn];
  15. bool mvc[2][maxn];
  16. queue<int> Q;
  17.  
  18. bool augment()
  19. {
  20.     for(int u=1;u<=m;u++)
  21.         if(!mx[u])
  22.         {
  23.             Q.push(u);
  24.             d[u]=0;
  25.         }
  26.         else d[u]=oo;
  27.  
  28.     d[0]=oo;
  29.  
  30.     int u;
  31.     while(Q.size())
  32.     {
  33.         u=Q.front(),Q.pop();
  34.  
  35.         for(const int &v: adx[u])
  36.             if(d[my[v]]==oo)
  37.             {
  38.                 d[my[v]]=d[u]+1;
  39.                 Q.push(my[v]);
  40.             }
  41.     }
  42.     return d[0]<oo;
  43. }
  44.  
  45. bool augmenting(const int &u)
  46. {
  47.     if(d[u]==oo) return false;
  48.  
  49.     for (const int &v: adx[u])
  50.         if(my[v]==0 || (d[my[v]]==d[u]+1 && augmenting(my[v])))
  51.         {
  52.             mx[u]=v;
  53.             my[v]=u;
  54.             return true;
  55.         }
  56.  
  57.     return false;
  58. }
  59.  
  60. int HKarp()
  61. {
  62.     int rep=0;
  63.     meset(mx,0);meset(my,0);
  64.     while(augment())
  65.         for(int u=1;u<=m;u++)
  66.             rep+=(mx[u])?0:augmenting(u);
  67.     return rep;
  68. }
  69.  
  70. void konig()
  71. {
  72.     meset(mvc,0);
  73.     queue<int> Qx,Qy;
  74.     for(int x=1;x<=m;x++) if(!mx[x]) Qx.push(x);
  75.     for(int y=1;y<=n;y++) if(!my[y]) Qy.push(y);
  76.  
  77.     int x,y;
  78.     while(Qx.size()+Qy.size())
  79.     {
  80.         if(Qx.size())
  81.         {
  82.             x=Qx.front(),Qx.pop();
  83.             for(const int &v :adx[x])
  84.                 if(!mvc[1][v])
  85.                     mvc[1][v]=1,Qx.push(my[v]);
  86.         }
  87.  
  88.         if(Qy.size())
  89.         {
  90.             y=Qy.front(),Qy.pop();
  91.             for(const int &u: ady[y])
  92.                 if(!mvc[0][u])
  93.                     mvc[0][u]=1,Qy.push(mx[u]);
  94.         }
  95.     }
  96.  
  97.     for(int u=1;u<=m;u++)
  98.         if(mx[u] && !mvc[0][u] && !mvc[1][mx[u]])
  99.             mvc[0][u]=1;
  100.  
  101.     cout<<"MIN MVC:\n";
  102.     for(int u=1;u<=m;u++) if(mvc[0][u]) cout<<u<<" ";
  103.     cout<<"\n";
  104.     for(int v=1;v<=n;v++) if(mvc[1][v]) cout<<v<<" ";
  105. }
  106. int main()
  107. {
  108.     #ifdef dmdd
  109.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  110.     #endif // dmdd
  111.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  112.     cin >> m >> n >> p;
  113.     int x,y;
  114.     while (cin>>x>>y)
  115.     {
  116.         adx[x].push_back(y);
  117.         ady[y].push_back(x);
  118.     }
  119.  
  120.     cout<<HKarp()<<"\n";
  121.     ///konig();
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0s 15848KB
comments (?)
stdin
copy 
8 7 12
1 1
1 4
2 1
2 2
2 4
3 2
3 3
4 2
4 3
5 5
2 8
1 7
stdout
copy 
5
https://ideone.com/E6iJ5A
language:
C++14 (gcc 8.3)
created:
6 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!