题意：
N个箱子排成一个圈，所有的箱子里的巧克力的数量加起来不大于N，每次可以把箱子里的巧克力向旁边的箱子转移（两个方向），问要让每个箱子里的巧克力不大于1的最小步数。
分析：
把巧克力大于1的箱子拆为 pi-1 个箱子（点），向没有巧克力的箱子建边，权值为最短距离。因为是一个圈，任意两点之间有两条路径，所以需要取小的一个值。X集合里的点的编号与原本图中的点无关，所以从0（1）开始，Y集合的点个数是N。
拆点很新颖，在完美匹配中，这是第一次遇到。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 //O(m*m*n) 8 const int N=1010, INF=0x3f3f3f3f; 9 int Map[N][N],mat1[N],mat2[N];//匹配上的左右集合 10 int KM(int m,int n) 11 { 12 int s[N],t[N],a[N],b[N]; 13 int i,j,k,p,q,ans=0; 14 for(i=0;i<m;i++) 15 { 16 a[i]=-INF; 17 for(j=0;j<n;j++) 18 a[i]=Map[i][j]>a[i]?Map[i][j]:a[i]; 19 if(a[i]==-INF) return -1;//cannot match 20 } 21 memset(b,0,sizeof(b)); 22 memset(mat1,-1,sizeof(mat1)); 23 memset(mat2,-1,sizeof(mat2)); 24 for(i=0;i<m;i++) 25 { 26 memset(t,-1,sizeof(t)); 27 p=q=0; 28 for(s[0]=i;p<=q&&mat1[i]<0;p++) 29 { 30 for(k=s[p],j=0;j<n&&mat1[i]<0;j++) 31 { 32 if(a[k]+b[j]==Map[k][j]&&t[j]<0) 33 { 34 s[++q]=mat2[j]; t[j]=k; 35 if(s[q]<0) 36 for(p=j;p>=0;j=p) 37 { 38 mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j; 39 } 40 } 41 } 42 } 43 if(mat1[i]<0) 44 { 45 i--,p=INF; 46 for(k=0;k<=q;k++) 47 { 48 for(j=0;j<n;j++) 49 if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p) 50 p=a[s[k]]+b[j]-Map[s[k]][j]; 51 } 52 for(j=0;j<n;j++) b[j]+=t[j]<0?0:p; 53 for(k=0;k<=q;k++) a[s[k]]-=p; 54 } 55 } 56 for(i=0;i<m;i++) ans+=Map[i][mat1[i]]; 57 return ans; 58 } 59 void init() 60 { 61 for(int i=0;i<N;i++) 62 for(int j=0;j<N;j++) 63 Map[i][j]=-INF; 64 } 65 int p[505]; 66 int main() 67 { 68 //freopen("test.txt","r",stdin); 69 int n,m,i,j,k,a,b,t; 70 while(scanf("%d",&n)!=EOF) 71 { 72 for(i=0;i<n;i++) scanf("%d",&p[i]); 73 init(); 74 t=0; 75 for(i=0;i<n;i++){ 76 if(p[i]<=1) continue; 77 for(k=p[i];k>1;k--) 78 { 79 for(j=0;j<n;j++){ 80 if(!p[j]){ 81 a=abs(j-i); 82 b=n-a; 83 a=min(a,b); 84 Map[t][j]=-a; 85 } 86 } 87 t++; 88 } 89 } 90 //for(i=0; i<t;i++){for(j=0;j<n;j++) printf("%d ",Map[i][j]);printf(" "); } 91 printf("%d ",-KM(t,n)); 92 } 93 return 0; 94 }