2879: [Noi2012]美食节
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1313 Solved: 708
[Submit][Status][Discuss]
Description
CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节共有n种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有m个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: 虽然这m个厨师都会制作全部的n种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用1, 2, ..., n依次编号，厨师用1, 2, ..., m依次编号，将第j个厨师制作第i种菜品的时间记为 ti,j 。小M认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第k道菜，则他的等待时间就是这个厨师制作前k道菜的时间之和。而总等待时间为所有同学的等待时间之和。现在，小M找到了所有同学的点菜信息: 有 pi 个同学点了第i种菜品（i=1, 2, ..., n）。他想知道的是最小的总等待时间是多少。
Input
输入文件的第1行包含两个正整数n和m，表示菜品的种数和厨师的数量。 第2行包含n个正整数，其中第i个数为pi，表示点第i种菜品的人数。 接下来有n行，每行包含m个非负整数，这n行中的第i行的第j个数为ti,j，表示第j个厨师制作第i种菜品所需的时间。 输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。
Output
输出仅一行包含一个整数，为总等待时间的最小值。
Sample Input
3 2
Sample Output
47
【样例说明】
【数据规模及约定】
#include<cstdio>
#define INF 1000000000
using namespace std;
int n,m,tot,edgenum,p,ans;
int vet[5000010],next[5000010],head[5000010],maxv[5000010],cost[5000010];
int dis[500010],flag[500010],q[500010],last[500010],pre[500010],a[110],t[110][110],id[110][1010],Id[110];
void add(int u,int v,int w,int z)
{
vet[++edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
maxv[edgenum]=w;
cost[edgenum]=z;
}
int spfa()
{
for (int i=0;i<=tot;i++){dis[i]=INF;flag[i]=0;}
int p1=-1,p2=0;
dis[0]=0;q[0]=0;flag[0]=1;
while (p1<p2)
{
int u=q[++p1];
flag[u]=0;
for (int e=head[u];e;e=next[e])
{
if (maxv[e]<=0) continue;
int v=vet[e];
if (dis[u]+cost[e]<dis[v])
{
dis[v]=dis[u]+cost[e];
last[v]=e;pre[v]=u;
if (!flag[v]){flag[v]=1;q[++p2]=v;}
}
}
}
if (dis[tot]==INF) return 0;else return 1;
}
void work()
{
ans+=dis[tot];
int u=pre[tot];
int p1=(u-1)/p+1,p2=(u-1)%p+1;
for (int i=1;i<=n;i++){add(Id[i],id[p1][p2+1],1,t[p1][i]*(p2+1));add(id[p1][p2+1],Id[i],0,-t[p1][i]*(p2+1));}
u=tot;
while (u)
{
int e=last[u];
maxv[e]--;
if (e%2) maxv[e+1]++;else maxv[e-1]++;
u=pre[u];
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)scanf("%d",&t[j][i]);
for (int i=1;i<=n;i++) p+=a[i];
for (int i=1;i<=m;i++)
for (int j=1;j<=p;j++)id[i][j]=++tot;
for (int i=1;i<=n;i++) Id[i]=++tot;tot++;
for (int i=1;i<=n;i++){add(0,Id[i],a[i],0);add(Id[i],0,0,0);}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){add(Id[i],id[j][1],1,t[j][i]);add(id[j][1],Id[i],0,-t[j][i]);}
for (int i=1;i<=m;i++)
for (int j=1;j<=p;j++){add(id[i][j],tot,1,0);add(tot,id[i][j],0,0);}
while (spfa()) work();
printf("%d\n",ans);
}
评论 (0)
