「BZOJ2879」[Noi2012] 美食节

2014年5月1日7,0374

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

题解

此题题目和修车几乎相同，但是数据范围扩了n倍

没做过修车的先做scoi2007修车

据说当时有人用dj+heap过了此题。。orz真心机智

这一题要考虑动态加边，大概就是

某位厨师在做倒数第k道菜后

再把他做倒数第k+1道菜的边加上

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 100001
using namespace std;
int n,m,tot,cnt=1,ans,t[45][105];
int c[45],d[100005],q[100005],from[100005],head[100005];
bool inq[100005];
struct edge{int from,to,next,c,v;}e[3000005];
void ins(int u,int v,int w,int c)
{
    cnt++;
    e[cnt].from=u;e[cnt].to=v;
    e[cnt].next=head[u];head[u]=cnt;
    e[cnt].c=c;e[cnt].v=w;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
    for(int i=0;i<=T;i++)d[i]=inf;
    int t=0,w=1;d[0]=0;inq[0]=1;q[0]=0;
    while(t!=w)
    {
        int now=q[t];t++;if(t==T)t=0;
        for(int i=head[now];i;i=e[i].next)
            if(e[i].v&&d[e[i].to]>d[now]+e[i].c)
            {
                d[e[i].to]=d[now]+e[i].c;from[e[i].to]=i;
                if(!inq[e[i].to])
                {inq[e[i].to]=1;q[w++]=e[i].to;if(w==T)w=0;} 
            }
        inq[now]=0; 
    }
    if(d[T]==inf)return 0;
    return 1;
}
void mcf()
{
    int x=inf,a,b,y;
    for(int i=from[T];i;i=from[e[i].from])
    {
        x=min(x,e[i].v);
        if(e[i].from==0)
            {y=e[i].to;a=(y-1)/tot+1;b=y%tot+1;}
    }
    for(int i=from[T];i;i=from[e[i].from])
        {e[i].v-=x;e[i^1].v+=x;ans+=e[i].c*x;}
    for(int i=1;i<=m;i++)
        insert((a-1)*tot+b,n*tot+i,1,b*t[i][a]);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
       scanf("%d",&c[i]);
       tot+=c[i];
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&t[i][j]);
    for(int i=1;i<=n*tot;i++)
        insert(0,i,1,0);
    for(int i=1;i<=m;i++)
        insert(n*tot+i,T,c[i],0);
    for(int i=1;i<=n;i++)
       for(int k=1;k<=m;k++)
          insert((i-1)*tot+1,n*tot+k,1,t[k][i]);
    while(spfa())mcf();
    printf("%d",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

#define T 100001

using namespace std;

int n,m,tot,cnt=1,ans,t[45][105];

int c[45],d[100005],q[100005],from[100005],head[100005];

bool inq[100005];

struct edge{int from,to,next,c,v;}e[3000005];

void ins(int u,int v,int w,int c)

{

cnt++;

e[cnt].from=u;e[cnt].to=v;

e[cnt].next=head[u];head[u]=cnt;

e[cnt].c=c;e[cnt].v=w;

}

void insert(int u,int v,int w,int c)

{ins(u,v,w,c);ins(v,u,0,-c);}

bool spfa()

{

for(int i=0;i<=T;i++)d[i]=inf;

int t=0,w=1;d[0]=0;inq[0]=1;q[0]=0;

while(t!=w)

{

int now=q[t];t++;if(t==T)t=0;

for(int i=head[now];i;i=e[i].next)

if(e[i].v&&d[e[i].to]>d[now]+e[i].c)

{

d[e[i].to]=d[now]+e[i].c;from[e[i].to]=i;

if(!inq[e[i].to])

{inq[e[i].to]=1;q[w++]=e[i].to;if(w==T)w=0;}

}

inq[now]=0;

}

if(d[T]==inf)return 0;

return 1;

}

void mcf()

{

int x=inf,a,b,y;

for(int i=from[T];i;i=from[e[i].from])

{

x=min(x,e[i].v);

if(e[i].from==0)

{y=e[i].to;a=(y-1)/tot+1;b=y%tot+1;}

}

for(int i=from[T];i;i=from[e[i].from])

{e[i].v-=x;e[i^1].v+=x;ans+=e[i].c*x;}

for(int i=1;i<=m;i++)

insert((a-1)*tot+b,n*tot+i,1,b*t[i][a]);

}

int main()

{

scanf("%d%d",&m,&n);

for(int i=1;i<=m;i++)

{

scanf("%d",&c[i]);

tot+=c[i];

}

for(int i=1;i<=m;i++)

for(int j=1;j<=n;j++)

scanf("%d",&t[i][j]);

for(int i=1;i<=n*tot;i++)

insert(0,i,1,0);

for(int i=1;i<=m;i++)

insert(n*tot+i,T,c[i],0);

for(int i=1;i<=n;i++)

for(int k=1;k<=m;k++)

insert((i-1)*tot+1,n*tot+k,1,t[k][i]);

while(spfa())mcf();

printf("%d",ans);

return 0;

}

« 「BZOJ1070」[SCOI2007] 修车「BZOJ3280」小R的烦恼 »

orz_hzwer

费用流有负权边用dij???

hzwer

听说dij可以通过一些方法滋瓷负权图

Alisa

黄学长，你的代码T了。。。

Alisa

貌似是oj的问题，没有事情啦

hzwer.com _ Home | http://hzwer.com

「BZOJ2879」[Noi2012] 美食节

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论