hdu 2282

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2282

思路：建图很重要，一个二分图最优匹配的题目。

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

View Code

  1 #include<iostream>
  2 const int MAXN=507;
  3 const int inf=1<<30;
  4 using namespace std;
  5 int match[MAXN];
  6 int map[MAXN][MAXN];
  7 int lx[MAXN],ly[MAXN];
  8 bool visitx[MAXN],visity[MAXN];
  9 int nx,ny;
 10 
 11 int Hungary(int u){
 12     visitx[u]=true;
 13     for(int i=0;i<ny;i++){
 14         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
 15             visity[i]=true;
 16             if(match[i]==-1||Hungary(match[i])){
 17                 match[i]=u;
 18                 return true;
 19             }
 20         }
 21     }
 22     return false;
 23 }
 24 
 25 
 26 void KM_prefect_match(){
 27     int tmp;
 28     for(int i=0;i<nx;i++){
 29         lx[i]=-inf;
 30     }
 31     memset(ly,0,sizeof(ly));
 32     for(int i=0;i<nx;i++){
 33         for(int j=0;j<ny;j++){
 34             lx[i]=max(lx[i],map[i][j]);
 35         }
 36     }
 37     for(int i=0;i<nx;i++)
 38     {
 39         while(1){
 40             memset(visitx,false,sizeof(visitx));
 41             memset(visity,false,sizeof(visity));
 42             if(Hungary(i))
 43                 break;
 44             else {
 45                 tmp=inf;
 46                 for(int j=0;j<nx;j++)if(visitx[j]){
 47                     for(int k=0;k<ny;k++){
 48                         if(!visity[k]&tmp>lx[j]+ly[k]-map[j][k]){
 49                             tmp=lx[j]+ly[k]-map[j][k];
 50                         }
 51                     }
 52                 }
 53                 for(int j=0;j<nx;j++){
 54                     if(visitx[j])
 55                         lx[j]-=tmp;
 56                 }
 57                 for(int j=0;j<ny;j++){
 58                     if(visity[j])
 59                         ly[j]+=tmp;
 60                 }
 61             }
 62         }
 63     }
 64 }
 65 
 66 
 67 
 68 int main(){
 69     int n;
 70     while(~scanf("%d",&n)){
 71         int num[MAXN],X[MAXN],Y[MAXN];
 72         memset(match,-1,sizeof(match));
 73         nx=ny=0;
 74         for(int i=0;i<n;i++){
 75             scanf("%d",&num[i]);
 76             if(!num[i]){
 77                 Y[ny++]=i;
 78             }else {
 79                 while(num[i]>1){
 80                     X[nx++]=i;
 81                     num[i]-=1;
 82                 }
 83             }
 84         }
 85         for(int i=0;i<nx;i++){
 86             for(int j=0;j<ny;j++){
 87                 map[i][j]=-inf;
 88             }
 89         }
 90         for(int i=0;i<nx;i++){
 91             for(int j=0;j<ny;j++){
 92                 map[i][j]=-min(abs(X[i]-Y[j]),n-(abs(X[i]-Y[j])));
 93             }
 94         }
 95         KM_prefect_match();
 96         int ans=0;
 97         for(int i=0;i<ny;i++){
 98             if(match[i]!=-1)
 99                 ans+=map[match[i]][i];
100         }
101         printf("%d\n",-ans);
102     }
103     return 0;
104 }