Chocolate HDU

Chocolate

题意：初始n块巧克力不均匀的放到n个盒子（环形）里，每次可以移动一块巧克力，问最少多少步使得每个盒子里有一块巧克力。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxv=510;
 4 const int inf=0x3f3f3f3f;
 5 
 6 int vb[maxv],vg[maxv],eb[maxv],eg[maxv];
 7 int c[maxv][maxv];
 8 int slack[maxv];
 9 int mc[maxv],L[maxv];
10 #define CLR(m,a) memset(m,a,sizeof(m))
11 
12 int num[maxv];
13 int cnt;
14 int n;
15 int dfs(int x){
16     vg[x]=1;
17     for(int i=0;i<n;i++){
18         if(vb[i]) continue;
19         int gap=eg[x]+eb[i]-c[x][i];
20         if(gap==0){
21             vb[i]=1;
22             if(mc[i]==-1||dfs(mc[i])){
23                 L[x]=i;
24                 mc[i]=x;
25                 return 1;
26             }
27         }
28         else slack[i]=min(slack[i],gap);
29     }
30     return 0;
31 }
32 int KM()
33 {
34     CLR(mc,-1);
35     CLR(L,-1);
36     CLR(eb,0);
37     for(int i=0;i<cnt;i++){
38         eg[i]=c[i][0];
39         for(int j=1;j<n;j++)
40         eg[i]=max(eg[i],c[i][j]);
41     }
42     for(int i=0;i<cnt;i++){
43         CLR(slack,inf);
44         while(1){
45             CLR(vb,0);
46             CLR(vg,0);
47             if(dfs(i)) break;
48             int d=inf;
49             for(int i=0;i<n;i++)  if(!vb[i]) d=min(d,slack[i]);
50             for(int i=0;i<cnt;i++) if(vg[i]) eg[i]-=d;
51             for(int i=0;i<n;i++){
52                 if(vb[i]) eb[i]+=d;
53                 else slack[i]-=d;
54             }
55         }
56     }
57     int ans=0;
58     for(int i=0;i<cnt;i++) if(L[i]!=-1)
59         ans+=c[i][L[i]];
60     return -ans;
61 }
62 int main(){
63     while(scanf("%d",&n)!=EOF){
64         for(int i=0;i<n;i++)
65             scanf("%d",&num[i]);
66         cnt=0;
67         for(int i=0;i<n;i++)
68         for(int j=0;j<num[i];j++){
69             for(int k=0;k<n;k++) c[cnt][k]=-min(abs(k-i),n-abs(k-i));
70             cnt++;
71         }
72         printf("%d
",KM());
73     }
74 }
View Code