[bzoj4873]寿司餐厅

时间:2022-06-10 09:30:50

来自FallDream的博客,未经允许,请勿转载,谢谢。


Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上,这家餐厅都会按顺序提供n种寿司,第i种寿司有一个代号ai和美味度di,i,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana也可以无限次取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段,即Kiana可以一次取走第1,2种寿司各一份,也可以一次取走第2,3种寿司各一份,但不可以一次取走第1,3种寿司。由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水果寿司一起吃就可能会肚子痛。因此,Kiana定义了一个综合美味度di,j(i<j),表示在一次取的寿司中,如果包含了餐厅提供的从第i份到第j份的所有寿司,吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间,所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时,不止一个综合美味度会被累加,比如若Kiana一次取走了第1,2,3种寿司各一份,除了d1,3以外,d1,2,d2,3也会被累加进总美味度中。神奇的是,Kiana的美食评判标准是有记忆性的,无论是单种寿司的美味度,还是多种寿司组合起来的综合美味度,在计入Kiana的总美味度时都只会被累加一次。比如,若Kiana某一次取走了第1,2种寿司各一份,另一次取走了第2,3种寿司各一份,那么这两次取寿司的总美味度d1,1+d2,2+d3,3+d1,2+d2,3,其中d2,2只会计算一次。奇怪的是,这家寿司餐厅的收费标准很不同寻常。具体来说,如果Kiana一共吃过了c(c>0)种代号为x的寿司,则她需要为这些寿司付出mx^2+cx元钱,其中m是餐厅给出的一个常数。现在Kiana想知道,在这家餐厅吃寿司,自己能获得的总美味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她不会算,所以希望由你告诉她。
n<=100 ai<=1000
 
貌似是叫最大权闭合子图
也就是如果你选了[i,j],你就必须选[i,j-1]和[i+1,j]
考虑最小割,先对于每一个编号建出一个点,从它向T连编号平方*m的边。
对于区间[i,j]
如果ij不等,先向[i,j-1][i+1,j]两个点连INF的边,然后如果点权正数就让答案加上它并且从S向它连点权的边,否则向T连点权的边。
如果ij相等,它的点权减去ai ,并且向它的编号对应节点连INF的边;和S,T的建边方法相同
然后最小割。
#include<iostream>
#include<cstdio>
#include<cstring>
#define S 0
#define MN 11001
#define INF (ll)1e18
#define num(x,y) (x-1)*n+y
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<='') x=x*+ch-'', ch=getchar();
return x*f;
} ll ans=;
int head[MN+],c[MN+],d[MN+],T,top,a[],q[MN+],cnt=,n,m,s[][];
struct edge{int to,next;ll w;}e[MN*]; inline void ins(int f,int t,ll w)
{
e[++cnt]=(edge){t,head[f],w};head[f]=cnt;
e[++cnt]=(edge){f,head[t],};head[t]=cnt;
} bool bfs()
{
memset(d,,sizeof(int)*(T+));int i,j;
for(d[q[top=i=]=S]=;i<=top;++i)
for(int j=c[q[i]]=head[q[i]];j;j=e[j].next)
if(e[j].w&&!d[e[j].to])
d[q[++top]=e[j].to]=d[q[i]]+;
return d[T];
} ll dfs(int x,ll f)
{
if(x==T) return f;ll used=;
for(int&i=c[x];i;i=e[i].next)
if(e[i].w&&d[e[i].to]==d[x]+)
{
int w=dfs(e[i].to,min(f-used,e[i].w));
used+=w;e[i].w-=w;e[i^].w+=w;
if(used==f) return f;
}
return d[x]=-,used;
} int main()
{
n=read();m=read();T=n*n+;
for(int i=;i<=;++i) ins(n*n+i,T,1LL*i*i*m);
for(int i=;i<=n;++i) a[i]=read();
for(int i=;i<=n;++i)
for(int j=i;j<=n;++j)
{
s[i][j]=read();
if(i!=j) ins(num(i,j),num(i+,j),INF),
ins(num(i,j),num(i,j-),INF);
else s[i][j]-=a[i],ins(num(i,j),n*n+a[i],INF);
if(s[i][j]>) ans+=s[i][j],ins(S,num(i,j),s[i][j]);
if(s[i][j]<) ins(num(i,j),T,-s[i][j]);
}
while(bfs()) ans-=dfs(S,INF);
printf("%lld\n",ans);
return ;
}

[bzoj4873]寿司餐厅的更多相关文章

  1. 【BZOJ4873】&lbrack;六省联考2017&rsqb;寿司餐厅(网络流)

    [BZOJ4873][六省联考2017]寿司餐厅(网络流) 题面 BZOJ 洛谷 题解 很有意思的题目 首先看到答案的计算方法,就很明显的感觉到是一个最大权闭合子图. 然后只需要考虑怎么构图就行了. ...

  2. 【BZOJ4873】&lbrack;Shoi2017&rsqb;寿司餐厅 最大权闭合图

    [BZOJ4873][Shoi2017]寿司餐厅 Description Kiana最近喜欢到一家非常美味的寿司餐厅用餐.每天晚上,这家餐厅都会按顺序提供n种寿司,第i种寿司有一个代号ai和美味度di ...

  3. 【最大权闭合子图】bzoj4873 &lbrack;Shoi2017&rsqb;寿司餐厅

    4873: [Shoi2017]寿司餐厅 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 369  Solved: 256[Submit][Status ...

  4. BZOJ4873&lbrack;Shoi2017&rsqb;寿司餐厅——最大权闭合子图

    题目描述 Kiana最近喜欢到一家非常美味的寿司餐厅用餐.每天晚上,这家餐厅都会按顺序提供n种寿司,第i种寿司有一个 代号ai和美味度di,i,不同种类的寿司有可能使用相同的代号.每种寿司的份数都是无 ...

  5. bzoj千题计划265:bzoj4873&colon; &lbrack;六省联考2017&rsqb;寿司餐厅

    http://www.lydsy.com/JudgeOnline/problem.php?id=4873 选a必选b,a依赖于b 最大权闭合子图模型 构图: 1.源点 向 正美味度区间 连 流量为 美 ...

  6. &lbrack;BZOJ4873&rsqb;&lbrack;六省联考2017&rsqb;寿司餐厅&lpar;最大权闭合子图&rpar;

    4873: [Shoi2017]寿司餐厅 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 490  Solved: 350[Submit][Status ...

  7. Bzoj4873 &lbrack;SXOI2017&rsqb;寿司餐厅

    Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 64  Solved: 45 Description Kiana最近喜欢到一家非常美味的寿司餐厅用餐.每 ...

  8. BZOJ4873 LuoguP3749 寿司餐厅

    题面太长,请诸位自行品尝—>寿司餐厅 分析: 首先题目中给了限制条件,假如选了D(i,j)(i<j),那么也就选了D(i+1,j)和D(i,j-1)两个点. 于是我们一下就明白了,哦,最大 ...

  9. bzoj4873&colon; &lbrack;Shoi2017&rsqb;寿司餐厅(最大权闭合子图)

    4873: [Shoi2017]寿司餐厅 大难题啊啊!!! 题目:传送门 题解:一眼题是网络流,但还是不会OTZ,菜啊... %题解... 最大权闭合子图!!! 好的...开始花式建边: 1.对于每个 ...

随机推荐

  1. SQL Server 存储&lpar;3&sol;8&rpar;:理解GAM和SGAM页

    我们知道SQL Server在8K 的页里存储数据.分区就是物理上连续的8个页.当我们创建一个数据库,数据文件会被逻辑分为页和区,当用户对象创建时,页会分配给它用来存储数据.GAM(Global Al ...

  2. Android zxing实现二维码生成和解析

    二维码的生成与解析.有多种途径.我选择用大品牌,google老大的zxing. gitHub链接是(我用的3.0.0,已经是nio了) https://github.com/zxing/zxing/t ...

  3. mybatis配置优化

    1.加入日志log4j 1)加入jar包:log4j-1.2.17.jar 2)加入log4j配置文件: 可以使properties或者xml形式 log4j.rootLogger = DEBUG,C ...

  4. SRS文档 王倩倩 201303014004

    设计阶段 Spec 图书管理系统functional spec:软件功能说明书, 主要用来说明软件的外部功能, 和用户的交互情况 (把软件当作一个黑盒子).从用户的角度描述软件产品的功能, 输入,输出 ...

  5. CLR via C&num; 内存管理读书记

    1. CLR 垃圾回收采用基于代的机制, 在一次垃圾回收中存活下来的对象被提升到另一代 2. 在确认对象是否垃圾时,从一组根开始,根包括静态字段,方法参数,局部变量等 3. 使用CriticalFin ...

  6. curl 简单使用

    cURL -- Command Line URL viewer -u username:password 以 Basic 方式发送用户名和密码 -d 以 POST 方式发送数据 -X 支持其它动词, ...

  7. JVM体系结构-----深入理解内存结构

    一.概述 内存在计算机中占据着至关重要的地位,任何运行时的程序或者数据都需要依靠内存作为存储介质,否则程序将无法正常运行.与C和C++相比,使用Java语言编写的程序并不需要显示的为每一个对象编写对应 ...

  8. cocos2d JS 艺术字特殊符号的显示

    this.setSocreAtion(score, this.tfMoneyList[index],mun); //传入分数与对象,调用下面的函数 setSocreAtion : function ( ...

  9. centos LVM详解

    title: centos LVM详解 date: 2018-04-24 14:00:03 tags: [linux,centos,LVM] --- 知识了解 LVM关系图 fdisk命令详解 [ro ...

  10. Go语言学习笔记(2)

    数组 var a [2]string a[0] = "Hello" a[1] = "World" primes := [6]int{2, 3, 5, 7, 11 ...