首页 > 代码库 > hdu2282 Chocolate 完美匹配 + 拆点

hdu2282 Chocolate 完美匹配 + 拆点

题意: 

  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 match20     }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("\n"); }91         printf("%d\n",-KM(t,n));92     }93     return 0;94 }
View Code

 

hdu2282 Chocolate 完美匹配 + 拆点