HDU_2228

这是一个二分图最优匹配的题目，但是一开始不知道怎么去构图，后来看了别人的思路之后不由得觉得构图十分巧妙。

如果我们要移动巧克力，最后一定是把盒子中多余的巧克力移到空盒子中去，那么我们不妨以多出的每个巧克力以及每个空盒子为研究对象，这样每个巧克力只能放到一个空盒子中，每个空盒子也只能放一个巧克力，于是就可以构成一个二分图去求最优匹配了，其中边权为巧克力和空盒子的最短距离。

当然为了能应用KM算法，我们在初始化边权的时候可以用MAXD减去最近距离作为边权，之后在统计结果的时候再将其还原即可。

#include
     
       #include
      
        #include
       
         #define MAXD 510 #define INF 1000000000 int a[MAXD], r[MAXD]; int G[MAXD][MAXD], N, nx, ny, yM[MAXD]; int A[MAXD], B[MAXD], slack; int visx[MAXD], visy[MAXD]; void init() {
   int i, j, p;     ny = 0; for(i = 0; i < N; i ++)     {
           scanf("%d", &a[i]); if(!a[i])             r[ny ++] = i;     }     nx = 0; for(i = 0; i < N; i ++) while(a[i] > 1)         {
   for(j = 0; j < ny; j ++)             {
                   p = abs(i - r[j]); if(N - p < p)                     p = N - p;                 G[nx][j] = MAXD - p;             }             a[i] --;             nx ++;         } } int searchpath(int u) {
   int v, temp;     visx[u] = 1; for(v = 0; v < ny; v ++) if(!visy[v])         {
               temp = A[u] + B[v] - G[u][v]; if(temp == 0)             {
                   visy[v] = 1; if(yM[v] == -1 || searchpath(yM[v]))                 {
                       yM[v] = u; return 1;                 }             } else if(temp < slack)                 slack = temp;         } return 0; } void EK() {
   int i, j, u; for(i = 0; i < nx; i ++)     {
           A[i] = 0; for(j = 0; j < ny; j ++) if(G[i][j] > A[i])                 A[i] = G[i][j];     }     memset(B, 0, sizeof(B));     memset(yM, -1, sizeof(yM)); for(u = 0; u < nx; u ++) for(;;)         {
               memset(visx, 0, sizeof(visx));             memset(visy, 0, sizeof(visy));             slack = INF; if(searchpath(u)) break; for(i = 0; i < nx; i ++) if(visx[i])                     A[i] -= slack; for(i = 0; i < ny; i ++) if(visy[i])                     B[i] += slack;         } } void printresult() {
   int i, res = 0; for(i = 0; i < ny; i ++) if(yM[i] != -1)             res += MAXD - G[yM[i]][i];     printf("%d\n", res); } int main() {
   while(scanf("%d", &N) == 1)     {
           init();         EK();         printresult();     } return 0; }