bzoj2879【NOI2012】美食节

 

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
3 1 1
5 7
3 6
8 9

Sample Output

47

【样例说明】
厨师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不会闲着，总等待时间更短。
可以证明，没有更优的点餐方案。


【数据规模及约定】
对于100%的数据，n <= 40, m <= 100, p <= 800, ti,j <= 1000（其中p = ∑pi，即点菜同学的总人数）。
每组数据的n、m和p值如下：
测试点编号 n m p
1 n = 5 m = 5 p = 10
2 n = 40 m = 1 p = 400
3 n = 40 m = 2 p = 300
4 n = 40 m = 40 p = 40
5 n = 5 m = 40 p = 100
6 n = 10 m = 50 p = 200
7 n = 20 m = 60 p = 400
8 n = 40 m = 80 p = 600
9 n = 40 m = 100 p = 800
10 n = 40 m = 100 p = 800

HINT

 

Source

 

 

 

 

费用流的应用

这道题和bzoj1070修车很像，但是数据范围很大，这就会使边和点很多，费用流算法就会超时。

我们考虑在那道题的基础上对构图方法进行一些优化。在SPFA算法中，每次只会找一条路径，也就是说每个厨师每次只会做一道菜。那么我们就可以在最初只加入每个厨师倒数第一道菜的边。之后每次操作，假设某个厨师做了倒数第x道菜，我们就加入这个厨师倒数第x+1道菜的边。这样就可以大大减少加入边的数量，正确性也是显然的。

这道题的优化方法很巧妙。

 

 

 

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 200000
#define maxm 2000000
#define inf 1000000000
using namespace std;
struct edge_type
{
	int from,to,next,v,c;
}e[maxm];
int head[maxn],dis[maxn],p[maxn],sum[maxn],f[maxn],a[41][101];
int n,m,ans=0,cnt=1,s,t,tot=0;
bool inq[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add_edge(int x,int y,int v,int c)
{
	e[++cnt]=(edge_type){x,y,head[x],v,c};head[x]=cnt;
	e[++cnt]=(edge_type){y,x,head[y],0,-c};head[y]=cnt;
}
inline bool spfa()
{
	queueq;
	memset(inq,false,sizeof(inq));
	F(i,1,t) dis[i]=inf;
	dis[s]=0;inq[s]=true;q.push(s);
	while (!q.empty())
	{
		int x=q.front();inq[x]=false;q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if (e[i].v&&dis[y]>dis[x]+e[i].c)
			{
				dis[y]=dis[x]+e[i].c;
				p[y]=i;
				if (!inq[y]){inq[y]=true;q.push(y);}
			}
		}
	}
	return dis[t]!=inf;
}
inline void mcf()
{
	while (spfa())
	{
		int tmp=inf;
		for(int i=p[t];i;i=p[e[i].from]) tmp=min(tmp,e[i].v);
		ans+=dis[t]*tmp;
		for(int i=p[t];i;i=p[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}
		int x=(e[p[t]].from-1)/tot+1,y=(x-1)*tot+(++sum[x]);
		add_edge(y,t,1,0);
		F(i,1,n) add_edge(m*tot+i,y,1,a[i][x]*sum[x]);
	}
}
int main()
{
	n=read();m=read();
	F(i,1,n){f[i]=read();tot+=f[i];}
	F(i,1,n) F(j,1,m) a[i][j]=read();
	s=1+m*tot+n;t=s+1;
	F(i,1,n) add_edge(s,m*tot+i,f[i],0);
	F(i,1,n) F(j,1,m) add_edge(m*tot+i,(j-1)*tot+1,1,a[i][j]);
	F(i,1,m) add_edge((i-1)*tot+1,t,1,0);
	F(i,1,m) sum[i]=1;
	mcf();
	printf("%d\n",ans);
}