/******************************************************
Kuhn－Munkras算法流程：
(1)初始化可行顶标的值 ；
(2)用匈牙利算法寻找完备匹配；
(3)若未找到完备匹配则修改可行顶标的值 ；
(4)重复(2)(3)直到找到相等子图的完备匹配为止 。
*******************************************************/
#define MAXINT  (int)((1u<<31) - 1)
#define MININT  (int)(-MAXINT - 1)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define N   (500)

int n;
bool x[N], y[N]; //是否检测标志
int lx[N], ly[N]; //lx[],ly[] 可行顶标，何谓“可行顶标”，即人为限制每次DFS各边应达到的权，当然要尽量大
int cost[N][N];  //weight[][] 二分图边权
int match[N];  //match[] 标记y[]所连接的x[]

/** 找增广路径，看各边能否达到可行顶标，标记*/
bool dfs(int v){
 int i = 0;
 int temp = 0;
 x[v] = true;
 for(i = 1; i <= n; i++){
  if(!y[i] && (lx[v] + ly[i]) == cost[v][i]){
   y[i] = true;
   temp = match[i];
   match[i] = v;
   if(temp == 0 || dfs(temp)){
    return true;
   }
   match[i] = temp;
  }
 }
 return false;
}

int KM(){
 int i = 0;
 int j = 0;
 int k = 0;
 int d = 0;
 int sum = 0;
 fill(lx + 1, lx + 1 + n, MININT);
 fill(ly + 1, ly + 1 + n, 0);
 fill(match + 1, match + 1 + n, 0);
 for(i = 1; i <= n; i++){
  for(j = 1; j <= n; j++){
   /** 初始化可行顶标，既是“人为”规定，当然应该越大越好*/
   lx[i] = MAX(lx[i], cost[i][j]);
  }
 }
 /** KM过程*/
 for(i = 1;i <= n; i++){
  do{
   fill(x + 1, x + 1 + n, false);
   fill(y + 1, y + 1 + n, false);
   if(dfs(i)){
    break;
   }
   d = MAXINT;
   for(j = 1; j <= n; j++){
    if(x[j]){
     for(k = 1; k <= n; k++){
      if(!y[k]){
       d = MIN(d, ((lx[j] + ly[k]) - cost[j][k]));
      }
     }
    }
   }
   /** 某些边无法匹配，说明“人为”规定的权太大，故减为比它小的最大权*/
   for(j = 1; j <= n; j++){
    if(x[j]){
     lx[j] -= d;
    }
    if(y[j]){
     ly[j] += d;
    }
   }
  }while(1);
 }
 sum = 0;
 for(i = 1; i <= n; i++){
  sum += cost[match[i]][i];
 }
 return sum;
}