Code:
1 class Solution { 2 public: 3 int sub; 4 int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) { 5 int N=workers.size(); 6 int M=bikes.size(); 7 vector<vector<int>> dis(N,vector<int>(M,0)); 8 vector<int> expw(N,INT_MIN); 9 vector<int> expb(M,0); 10 for(int i=0;i<N;++i){ 11 for(int j=0;j<M;++j){ 12 dis[i][j]=-(abs(workers[i][0]-bikes[j][0])+abs(workers[i][1]-bikes[j][1])); 13 expw[i]=max(expw[i],dis[i][j]); 14 } 15 } 16 vector<int> bmat(M,-1); 17 18 for(int i=0;i<N;++i){ 19 while(true){ 20 vector<bool> wvisit(N,false); 21 vector<bool> bvisit(M,false); 22 sub=INT_MAX; 23 if(dfs(i,wvisit,bvisit,dis,expw,expb,bmat)){ 24 break; 25 } 26 27 for(int j=0;j<N;++j){ 28 if(wvisit[j]){ 29 expw[j]-=sub; 30 } 31 } 32 for(int j=0;j<M;++j){ 33 if(bvisit[j]){ 34 expb[j]+=sub; 35 } 36 } 37 } 38 } 39 40 int res=0; 41 for(int i=0;i<M;++i){ 42 if(bmat[i]!=-1){ 43 res+=dis[bmat[i]][i]; 44 } 45 } 46 return -res; 47 } 48 49 bool dfs(int w, vector<bool> &wvisit, vector<bool> &bvisit, 50 vector<vector<int>> &dis, vector<int> &expw, vector<int> &expb, vector<int> &bmat){ 51 wvisit[w]=true; 52 for(int i=0;i<dis[0].size();++i){ 53 if(bvisit[i]) continue; 54 int diff=expw[w]+expb[i]-dis[w][i]; 55 if(diff==0){ 56 bvisit[i]=true; 57 if(bmat[i]==-1 || dfs(bmat[i],wvisit,bvisit,dis,expw,expb,bmat)){ 58 bmat[i]=w; 59 return true; 60 } 61 }else{ 62 sub=min(sub,diff); 63 } 64 } 65 return false; 66 } 67 };