2195(3).cpp

各种算法

#include <cstdio> 
#include <queue> 
#include <algorithm> 
using namespace std;			//O(N^3)

const int N = 128; 
#define INF (int)((unsigned int)(-1)>>1)
 
class Graph { 
private: 
   bool xckd[N], yckd[N]; 
   int n, edge[N][N], xmate[N], ymate[N]; 
   int lx[N], ly[N], slack[N], prev[N]; 
   queue<int> Q; 
   bool bfs(); 
   void agument(int); 
public: 
   bool make(); 
   int KMMatch(); 
}; 
bool Graph::make() { 
   int house[N], child[N], h, w, cn = 0; int i,j;
   char line[N]; 
   scanf("%d %d", &h, &w); 
   if(w == 0) return false; 
   scanf("\n"); n = 0; 
   for(	 i = 0; i < h; i++) { 
      gets(line); 
      for(int j = 0; line[j] != 0; j++) { 
         if(line[j] == 'H') house[n++] = i * N + j; 
         if(line[j] == 'm') child[cn++] = i * N + j; 
      } 
   } 
   for(	 i = 0; i < n; i++) { 
      int cr = child[i] / N, cc = child[i] % N; 
      for(	 j = 0; j < n; j++) { 
         int hr = house[j] / N, hc = house[j] % N; 
         edge[i][j] = -abs(cr-hr) - abs(cc-hc); 
      } 
   } 
   return true; 
} 
bool Graph::bfs() {			//移位操作 用到状态压缩思想
   while(!Q.empty()) { 
      int p = Q.front(), u = p>>1; Q.pop();		//队列元素末位1用于辨别元素为y方
      if(p&1) { 
         if(ymate[u] == -1) { agument(u); return true; } 
         else { xckd[ymate[u]] = true; Q.push(ymate[u]<<1); } 
      } 
	  else { 
         for(int i = 0; i < n; i++) 
            if(yckd[i]) continue; 
            else 
				if(lx[u]+ly[i] != edge[u][i]) { 
					int ex = lx[u]+ly[i]-edge[u][i]; 
					if(slack[i] > ex) { slack[i] = ex; prev[i] = u; } 
				}	
				else { 
					yckd[i] = true; prev[i] = u; 
					Q.push((i<<1)|1); 
				} 
      } 
   } 
   return false; 
} 
void Graph::agument(int u) { //构造交错树
   while(u != -1) { 
      int	pv = xmate[prev[u]]; 
		ymate[u] = prev[u]; 
			xmate[prev[u]] = u; 
			u = pv; 
   } 
} 
int Graph::KMMatch() { 
   memset(ly, 0, sizeof(ly)); int i,j;
   for(	 i = 0; i < n; i++) { 
      lx[i] = -INF; 
      for(	 j = 0; j < n; j++) lx[i] = lx[i] < edge[i][j]?edge[i][j]:lx[i]; 
   } 
   memset(xmate, -1, sizeof(xmate)); memset(ymate, -1, sizeof(ymate)); 
   bool agu = true; 
   for(int mn = 0; mn < n; mn++) { 
      if(agu) { 
         memset(xckd, false, sizeof(xckd)); 
         memset(yckd, false, sizeof(yckd)); 
         for(	i = 0; i < n; i++) slack[i] = INF; 
         while(!Q.empty()) Q.pop(); 
         xckd[mn] = true; Q.push(mn<<1); 
      } 
      if(bfs()) { agu = true; continue; } 
      int ex = INF; mn--; agu = false; 
      for(	 i = 0; i < n; i++) 
		  if(!yckd[i]) ex = ex > slack[i]?slack[i]:ex;//ex <?= slack[i]; 
      for(	 i = 0; i < n; i++) { 
         if(xckd[i]) lx[i] -= ex; 
         if(yckd[i]) ly[i] += ex; 
         slack[i] -= ex;				//同步更新slack[y]
      } 
      for(	 i = 0; i < n; i++) 
         if(!yckd[i] && slack[i] == 0) { yckd[i] = true; Q.push((i<<1)|1); } 
   } 
   int cost = 0; 
   for(	 i = 0; i < n; i++) cost += edge[i][xmate[i]]; 
   return cost; 
} 
  
int main() 
{ 
   Graph g; 

   while(g.make()) printf("%d\n", -g.KMMatch()); 
    
   return 0; 
}