[BZOJ2879] [Noi2012] 美食节 (费用流 & 动态加边)

时间:2022-08-27 09:37:14

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

Solution

  和$BZOJ1070$其实是一道题,只不过这道题强制动态加边,并不知道为什么第$2$个点会$TLE$,总之$BZOJ$可以$AC$

 #include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, v, w, c, nxt;
}e[];
int n, fst[], t[][], etot = , level[];
int q[], belong[], fin[], pth[], use;
bool inq[]; void addedge(int u, int v, int w, int c)
{
e[++etot] = (edge){u, v, w, c, fst[u]}, fst[u] = etot;
e[++etot] = (edge){v, u, , -c, fst[v]}, fst[v] = etot;
} bool SPFA()
{
int front = , back, u;
memset(level, , sizeof(level));
level[n + ] = ;
q[back = ] = n + , inq[n + ] = true;
while(front != back)
{
u = q[(++front % )];
front %= , inq[u] = false;
for(int i = fst[u]; i; i = e[i].nxt)
if(e[i].w && level[e[i].v] > level[u] + e[i].c)
{
level[e[i].v] = level[u] + e[i].c;
pth[e[i].v] = i;
if(!inq[e[i].v])
{
q[(++back % )] = e[i].v;
back %= , inq[e[i].v] = true;
}
}
}
return level[n + ] < ;
} int Edmond_Karp()
{
for(int i = pth[n + ]; i; i = pth[e[i].u])
{
--e[i].w, ++e[i ^ ].w;
if(e[i].u == n + ) use = e[i].v;
}
return level[n + ];
} int main()
{
int m, tmp, ans = , ptot;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i)
{
scanf("%d", &tmp);
addedge(i, n + , tmp, );
}
for(int i = ; i <= n; ++i)
for(int j = ; j <= m; ++j)
scanf("%d", &t[i][j]);
ptot = n + ;
for(int i = ; i <= m; ++i)
{
belong[++ptot] = i, ++fin[i];
for(int j = ; j <= n; ++j)
addedge(ptot, j, , t[j][i]);
addedge(n + , ptot, , );
}
while(SPFA())
{
ans += Edmond_Karp();
tmp = belong[++ptot] = belong[use], ++fin[tmp];
for(int i = ; i <= n; ++i)
addedge(ptot, i, , t[i][tmp] * fin[tmp]);
addedge(n + , ptot, , );
}
printf("%d\n", ans);
return ;
}

[BZOJ2879] [Noi2012] 美食节 (费用流 & 动态加边)的更多相关文章

  1. 【bzoj2879】&lbrack;Noi2012&rsqb;美食节 费用流&plus;动态加边

    原文地址:http://www.cnblogs.com/GXZlegend 题目描述 CZ市为了欢迎全国各地的同学,特地举办了一场盛大的美食节.作为一个喜欢尝鲜的美食客,小M自然不愿意错过这场盛宴.他 ...

  2. BZOJ 2879&colon; &lbrack;Noi2012&rsqb;美食节&lpar; 费用流 &plus; 动态加边 &rpar;

    倒着做菜..然后考虑为当前的人做菜对后面的人的影响就可以了..要动态加边 --------------------------------------------------------------- ...

  3. &lbrack;NOI2012&rsqb;&lbrack;bzoj2879&rsqb; 美食节 &lbrack;费用流&plus;动态加边&rsqb;

    题面 传送门 思路 先看看这道题 修车 仔细理解一下,这两道题是不是一样的? 这道题的不同之处 但是有一个区别:本题中每一种车有多个需求,但是这个好办,连边的时候容量涨成$p\lbrack i\rbr ...

  4. &lbrack;BZOJ2879&rsqb;&lbrack;NOI2012&rsqb;美食节&lpar;费用流&rpar;

    设sm为所有p之和,套路地对每道菜建一个点,将每个厨师拆成sm个点,做的倒数第i道菜的代价为time*i. S向每道菜连边<0,p[i]>(前者为代价后者为流量),i菜到j厨师的第k个点连 ...

  5. BZOJ 2879 &lbrack;Noi2012&rsqb;美食节 &vert; 费用流 动态开点

    这道题就是"修车"的数据加强版--但是数据范围扩大了好多,应对方法是"动态开点". 首先先把"所有厨师做的倒数第一道菜"和所有菜连边,然后跑 ...

  6. &lbrack;NOI2012&rsqb;美食节——费用流(带权二分图匹配)&plus;动态加边

    题目描述 小M发现,美食节共有n种不同的菜品.每次点餐,每个同学可以选择其中的一个菜品.总共有m个厨师来制作这些菜品.当所有的同学点餐结束后,菜品的制作任务就会分配给每个厨师.然后每个厨师就会同时开始 ...

  7. BZOJ 2879 美食节(费用流-动态加边)

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2879 题意:有n道菜,每道菜需要b[i]份,m个厨师,第j个厨师做第i道菜需要时间a[i ...

  8. &lbrack;NOI2012&rsqb;美食节&lpar;费用流&rpar;

    题目描述 CZ市为了欢迎全国各地的同学,特地举办了一场盛大的美食节.作为一个喜欢尝鲜的美食客,小M自然不愿意错过这场盛宴.他很快就尝遍了美食节所有的美食.然而,尝鲜的欲望是难以满足的.尽管所有的菜品都 ...

  9. &lbrack;BZOJ1070&rsqb; &lbrack;SCOI2007&rsqb; 修车 &lpar;费用流 &amp&semi; 动态加边&rpar;

    Description 同一时刻有N位车主带着他们的爱车来到了汽车维修中心.维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的.现在需要安排这M位技术人员所维修的车及顺序,使 ...

随机推荐

  1. Android 自定义spinner下拉框实现的实现

    请支持原创:http://blog.csdn.NET/geniuseoe2012/article/details/8723702 说到Android下拉框spineer,框架中虽有现成的控件,但实际效 ...

  2. servlet生成随机验证码

    package com.cgyue; import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import jav ...

  3. Drupal 7&period;31 SQL注射分析POC

    此漏洞昨日爆发 ,我们有时间去看看今天的代码. 于Drupal于,跑sql声明使用PDO型号,这是一般能够避免大部分的注射,由于使用占位符的sql语法语句是限制. 但是,这并不意味着绝对安全,. 在D ...

  4. 一道风骚的DP

    也是校赛学长出的一道题~想穿了很简单..但我还是听了学长讲才明白. 观察力有待提高. Problem D: YaoBIG's extra homeworkTime LimitMemory Limit1 ...

  5. Python学习&lowbar;09&lowbar;模块

    模块 模块是python中的最高组织单元,在物理层面上,模块以文件存储,模块的文件名就是模块的名字.py,每个模块都有自己的名称空间. python按照路径搜索来查找模块文件,在PYTHONPATH环 ...

  6. CodeFirst之深入了解EntityFramework

    一.概要 本文在基于CodeFirst思想之上 深入了解EntityFramework.其实我个人一直头疼的问题就是每次Entity类一有变动,无论是新增表,更改表结构等 EF一律把数据库删掉重建,这 ...

  7. EMF32名词解释

    (EFM32)32位节能微控制器(Energy Friendly Microcontroller 32-bit) (Gecko)壁虎 (Starter Kit)入门套件 (STK)入门套件 (Debu ...

  8. linux简单安装方法

    一.配置静态IP NAT:模式: 修改网卡eth0 vim /etc/sysconfig/network-scripts/ifcfg-eth0 内容如下: DEVICE=eth0 HWADDR=:0C ...

  9. phpstudy集成下Apache配置部署https安全证书

    一..先申请到安全证书.(腾讯云或者阿里云申请免费1年的安全证书),怎么申请这里也说下(以腾讯云为例): 1.登录腾讯云QQ或微信登录都行,第一次登录要通过实名认证,点击[产品]---[ss证书l] ...

  10. jquery validation表单验证插件。

    这个是刚学的,觉得对以后挺有用的,就想把自己所学的分享一下. 校验规则: (1)required:true 必输字段 (2)number:true 必须输入合法的数字(负数,小数) (3)digits ...