[NOI2012]美食节

题目

题目描述

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）。他想知道的是最小的总等待时间是多少。

输入输出格式

输入格式：

输入文件的第1行包含两个正整数n和m，表示菜品的种数和厨师的数量。第2行包含n个正整数，其中第i个数为pi，表示点第i种菜品的人数。接下来有n行，每行包含m个非负整数，这n行中的第i行的第j个数为ti,j，表示第j个厨师制作第i种菜品所需的时间。输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。

输出格式：

输出仅一行包含一个整数，为总等待时间的最小值。

输入输出样例

输入样例#1：

输出样例#1：

说明

厨师1先制作1份菜品2，再制作2份菜品1。点这3道菜的3个同学的等待时间分别为3，3+5=8，3+5+5=13。

厨师2先制作1份菜品1，再制作1份菜品3。点这2道菜的2个同学的等待时间分别为7，7+9=16。

总等待时间为3+8+13+7+16=47。

虽然菜品1和菜品3由厨师1制作更快，如果这些菜品都由厨师1制作，总等待时间反而更长。如果按上述的做法，将1份菜品1和1份菜品3调整到厨师2制作，这样厨师2不会闲着，总等待时间更短。

可以证明，没有更优的点餐方案。每组数据的n、m和p值如下：

测试点编号	n	m	p
1	5	5	10
2	40	1	400
3	40	2	300
4	40	40	40
5	5	40	100
6	10	50	200
7	20	60	400
8	40	80	600
9	40	100	800
10	40	100	800

对于100%的数据，n <= 40, m <= 100, p <= 800, ti,j <= 1000 （其中p = ∑pi）

题解

类似的题目

设一个厨师做菜顺序是：$1,2,3,4,5,…,n$

那么等待时间就是$\sum_{1}^{n}cost_i(n-i+1)=ncost_1+(n-1)cost_2+…+cost_n$

所以思路是将厨师拆成$n\times m$个点，然后源点$\rightarrow$菜$\rightarrow n$个厨师，花费为$i$倍$\rightarrow$汇点

因为一个菜可能多个人选，所以菜$\rightarrow$厨师的流量为这个菜被选的次数

还有点的个数也要注意，这里不再赘述

但是还有个问题，这样会$T$…

发现这么跑最多要跑$6e6$次$SPFA$

这里就用到了一个神奇的东西：动态加点

发现$i-1$的菜怎么选影响$i$的菜的选择，而$i$的菜选择不会影响$i-1$菜的选择

所以可以把第一层先建好，跑一遍$SPFA$，找出这时候增广的点，建ta的下一层点，然后再跑

这样就能过了

代码

# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
using namespace std;
const int MAX=2e5+1,inf=1e8;
struct p{
    int x,y,dis,cn;
}c[MAX<<6];
int n,m,num=2,tot1,t,tot;
int h[MAX],d[MAX],pre[MAX],T[101];
int a[41][101];
bool use[MAX];
void add(int x,int y,int dis,int cn)
{
    c[num]=(p){h[y],x,0,-cn},h[y]=num++;
    c[num]=(p){h[x],y,dis,cn},h[x]=num++;
}
void EK()
{
    while(1)
    {
        queue<int> qu;
        qu.push(0);
        memset(d,1,sizeof(d));
        d[0]=0;
        while(!qu.empty())
        {
            int tt=qu.front();
            qu.pop();
            use[tt]=0;
            for(int i=h[tt];i;i=c[i].x)
              if(c[i].dis&&d[c[i].y]>d[tt]+c[i].cn)
              {
              	d[c[i].y]=d[tt]+c[i].cn;
              	pre[c[i].y]=i;
              	if(!use[c[i].y])
              	{
              		use[c[i].y]=1;
              		qu.push(c[i].y);
                }
              }
        }
        if(d[t]>1e6) return;
        int hh=t,sum=inf;
        while(pre[hh])
        {
            int l=pre[hh];
            sum=min(sum,c[l].dis);
            hh=c[l^1].y;
        }
        hh=t;
        while(pre[hh])
        {
            int l=pre[hh];
            c[l].dis-=sum;
            c[l^1].dis+=sum;
            tot1+=sum*c[l].cn;
            hh=c[l^1].y;
        }
        int x=c[pre[t]^1].y;
        add(x+1,t,1,0);
        for(int i=1;i<=n;++i)
          add(i+tot*m,x+1,1,a[i][x/tot+1]*(x%tot+1));
    }
}
int read()
{
	int x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
      tot+=(T[i]=read());
    t=tot*(m+1)+1;
    for(int i=1;i<=m;++i)
      add((i-1)*tot+1,t,1,0);
    for(int i=1;i<=n;++i)
      for(int j=1;j<=m;j++)
        {
        	a[i][j]=read();
        	add(i+tot*m,(j-1)*tot+1,1,a[i][j]);
	  	}
	for(int i=1;i<=n;++i)
	  add(0,i+tot*m,T[i],0);
    EK();
    printf("%d",tot1);
    return 0;
}

题目