标签：网络流

题目

题目传送门

Description

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想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。

由于她不会算，所以希望由你告诉她

Input

第一行包含两个正整数n,m，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。

第二行包含n个正整数，其中第k个数ak表示第k份寿司的代号。

接下来n行，第i行包含n-i+1个整数，其中第j个数di,i+j-1表示吃掉寿司能获得的相应的美味度，具体含义见问题描述。

Output

输出共一行包含一个正整数，表示Kiana能获得的总美味度减去花费的总钱数的最大值。

输入输出样例

输入样例#1

1
2
3
4
5
3 1
2 3 2
5 -10 15
-10 15
15

输出样例#1

1
12

输入样例#2

1
2
3
4
5
6
7
5 0
1 4 1 3 4
50 99 8 -39 30
68 27 -75 -32
70 24 72
-10 81
-95

输出样例#2

1
381

输入样例#3

1
2
3
4
5
6
7
8
9
10
11
12
10 1
5 5 4 4 1 2 5 1 5 3
83 91 72 29 22 -5 57 -14 -36 -3
-11 34 45 96 32 73 -1 0 29
-48 68 44 -5 96 66 17 74
88 47 69 -9 2 25 -49
86 -9 -77 62 -10 -30
2 40 95 -74 46
49 -52 2 -51
-55 50 -44
72 22
-68

输出样例#3

1
1223

说明

【样例1说明】

在这组样例中，餐厅一共提供了3份寿司，它们的代号依次为a1=2，a2=3，a3=2，计算价格时的常数m=1。在保证每次取寿司都能获得新的美味度的前提下，Kiana一共有14种不同的吃寿司方案：

1. Kiana一个寿司也不吃，这样她获得的总美味度和花费的总钱数都是0，两者相减也是0；

2. Kiana只取1次寿司，且只取第1个寿司，即她取寿司的情况为{[1,1]}，这样获得的总美味度为5，花费的总钱数为1-2^2+1*2=6，两者相减为-1；

3. Kiana只取1次寿司，且只取第2个寿司，即她取寿司的情况为{[2,2]}，这样获得的总美味度为-10，花费的总钱数为1-3^2+1*3=12，两者相减为-22；

4. Kiana只取1次寿司，且只取第3个寿司，即她取寿司的情况为{[3,3]}，这样获得的总美味度为15，花费的总钱数为1* 2^2+1*2=6，两者相减为9；

5. Kiana只取1次寿司，且取第1,2个寿司，即她取寿司的情况为{[1,2]}，这样获得的总美味度为5+(-10)+(-10)=-15，花费的总钱数为(1-2^2+1*2)+(1-3^2+1*3)=18，两者相减为-33；

6. Kiana只取1次寿司，且取第2,3个寿司，即她取寿司的情况为{[2,3]}，这样获得的总美味度为(-10)+15+15=20，花费的总钱数为(1-2^2+1*2)+(1*3^2+1*3)=18，两者相减为2；

7. Kiana只取1次寿司，且取第1,2,3个寿司，即她取寿司的情况为{[1,3]}，这样获得的总美味度为5+(-10)+15+(-10)+15+15=30，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为10。

8. Kiana取2次寿司，第一次取第1个寿司，第二次取第2个寿司，即她取寿司的情况为{[1,1],[2,2]}，这样获得的总美味度为5+(-10)=-5，花费的总钱数为(1*2^2+1*2)+(1*3^2+1*3)=18，两者相减为-23；

9. Kiana取2次寿司，第一次取第1个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,1],[3,3]}，这样获得的总美味度为5+15=20，花费的总钱数为1* 2^2+2 * 2=8，两者相减为12；

10. Kiana取2次寿司，第一次取第2个寿司，第二次取第3个寿司，即她取寿司的情况为{[2,2],[3,3]}，这样获得的总美味度为(-10)+15=5，花费的总钱数为(1*2^2+1*2)+(1* 3^2+1*3)=18，两者相减为-13；

11. Kiana取2次寿司，第一次取第1,2个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,2],[3,3]}，这样获得的总美味度为5+(-10)+(-10)+15=0，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为-20；

12. Kiana取2次寿司，第一次取第1个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,1],[2,3]}，这样获得的总美味度为5+(-10)+15+15=25，花费的总钱数为(1-22+2-2)+(1-32+1-3)=20，两者相减为5；

13. Kiana取2次寿司，第一次取第1,2个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,2],[2,3]}，这样获得的总美味度为5+(-10)+15+(-10)+15=15，花费的总钱数为(1* 2^2+2* 2)+(1* 3^2+1*3)=20，两者相减为-5；

14. Kiana取3次寿司，第一次取第1个寿司，第二次取第2个寿司，第三次取第3个寿司，即她取寿司的情况为{[1,1],[2,2],[3,3]}，这样获得的总美味度为5+(-10)+15=10，花费的总钱数为(1* 2^2+2* 2)+(1* 3^2+1*3)=20，两者相减为-10。

所以Kiana会选择方案9，这时她获得的总美味度减去花费的总钱数的值最大为12。

N<=100,Ai<=1000

题意

语文阅读理解题，所以我善良地写个简易题面

N个寿司，每个寿司有相应的代号x

下面给出一个n*n的邻接矩阵，d[i][j]表示吃第i到第j个寿司可以获得的美味度

当然，相应的寿司需要花费一定量的金钱

具体来说，如果一共吃过了 c(c > 0) 种代号为 x 的寿司，则她需要为这些寿司付出

最大化美味度-金钱

分析

显然，这是一个最大权闭合子图问题

最大权闭合子图模型

1. 选一些点必须要选其他点
2. 每个点最多选一次
3. 有点权
4. 求最大点权和

就是网络流24题中的太空飞行计划问题

可以参见517的博文

针对本题

直接上建模构图方式

1. 超级源点S向正美味度的区间连一条流量为美味度的边
2. 负美味度区间向超级汇点连一条流量为美味度绝对值的边
3. 区间[i,j]向区间[i+1,j],[i,j-1]分别连一条流量为inf的边
4. 区间[i,i]向寿司i连一条流量为inf的边
5. 寿司i向超级汇点连一条流量为寿司代号的边
6. 寿司i向其代号连一条流量为inf的边
7. 寿司代号i向超级汇点连一条流量为m*i*i的边

然后求最小割即可

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
    ll f=1,x=0;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;
}
//**********head by yjjr**********
#define inf 0x3fffffff
const int maxn=1e4+6;
int a[maxn],d[maxn][maxn],id1[1006][1006],id2[maxn],id3[maxn];
int last[maxn],n,m,cnt=1,S=0,T=maxn-1,que[maxn],h[maxn],ans,id=0;
bool vis[maxn];
struct edge{int to,next,v;}e[maxn<<2];
void insert(int u,int v,int w){
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
inline bool bfs(){
    int head=0,tail=1,now;
    mem(h,-1);que[0]=S,h[S]=0;
    while(head<tail){
        now=que[head++];
        reg(now)
            if(e[i].v&&h[e[i].to]==-1){h[e[i].to]=h[now]+1;que[tail++]=e[i].to;}
    }
    if(h[T]==-1)return 0;else return 1;
}
inline int dfs(int x,int f){
    if(x==T)return f;
    int w,used=0;
    reg(x)
        if(e[i].v&&h[e[i].to]==h[x]+1){
            w=dfs(e[i].to,min(e[i].v,f-used));
            e[i].v-=w,e[i^1].v+=w;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}       
void dinic(){while(bfs())ans-=dfs(S,inf);}
int main()
{
    n=read(),m=read();
    rep(i,1,n)a[i]=read();
    rep(i,1,n)
        rep(j,i,n){
            d[i][j]=read();
            if(d[i][j]>0)ans+=d[i][j];
        }
    rep(i,1,n)rep(j,i,n)id1[i][j]=++id;
    rep(i,1,n)id2[i]=++id;
    rep(i,1,n)
        if(!vis[a[i]])vis[a[i]]=true,id3[a[i]]=++id;
    rep(i,1,n)
        rep(j,i,n){
            if(d[i][j]>0)insert(S,id1[i][j],d[i][j]);else insert(id1[i][j],T,-d[i][j]);
            if(i!=j)insert(id1[i][j],id1[i+1][j],inf),insert(id1[i][j],id1[i][j-1],inf);
        }
    rep(i,1,n)insert(id1[i][i],id2[i],inf);
    rep(i,1,n)insert(id2[i],id3[a[i]],inf),insert(id2[i],T,a[i]);
    if(m)rep(i,1,1000)if(vis[i])insert(id3[i],T,i*i);
    dinic();
    cout<<ans<<endl;
    return 0;
}

最后

以上就是高高野狼最近收集整理的关于洛谷3749 [六省联考2017]寿司餐厅题目题意分析code的全部内容，更多相关洛谷3749内容请搜索靠谱客的其他文章。