Hi I am getting TLE in the 7th test case. How do I optimize my code? Problem link: http://www.spoj.com/problems/MATCHING/
#include<cstdio> #include<algorithm> #include<iostream> #include<vector> #include<set> #include<cstring> using namespace std; #define in(a) scanf("%d",&a); #define pb push_back vector <int> G[50000+5]; bool seen[50000+5]; int matchL[50000+5],matchR[50000+5],A[50000+5]; int n,m; bool bpm(int u) { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(seen[v]) continue; seen[v]=true; if(matchR[v]<0 || bpm( matchR[v] )) { matchR[v]=u; matchL[u]=v; return true; } } return false; } int main() { int n,m,p; set<int> row; set<int> col; set<int>::iterator it; int pos=0; in(n);in(m);in(p); while(p--) { int x,y; in(x);in(y); if(row.find(x)==row.end()){ row.insert(x); A[pos++]=x; } G[x].pb(y); } /*for(int i=0;i<10;i++) cout<<A[i]<<" "; cout<<endl;*/ memset(matchL,-1,sizeof(matchL)); memset(matchR,-1,sizeof(matchR)); m=row.size(); //n=B.size(); int cnt=0; for(int i=0;i<m;i++) { memset(seen,0,sizeof(seen)); if( bpm( A[i] ) ) cnt++; } printf("%d\n",cnt); return 0; }
It's obiviously that your solution can get TLE. The command "memset(seen,0,sizeof(seen))" is called exactly m times (m<=50000). It's impossible to memset an array of size 50000 for 50000 times in 3s.
You should also notice that, this problem can't be solved by regular max-matching algorithm. You must use Hoftcroft-Karp or Dinitz to solve it.