[文章目录]
Description
这家餐厅都会按顺序提供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）
记得省选的时候我还不会网络流，哭死在考场。（继NOIP2016我还不会链式前向星第二次哭死），不过可能是这道题自省选以来放脑袋里太久了吧，竟然自己想出来建图方案了，1A，爽！！！！
由于题目描述说美味度-钱数最大值，很容易想到具有代价统一化的思想的最大全闭合子图。虽然题目描述我个人理解的不是太好，但样例很明白啊，（本以为可以重复取相同的一段）。
建图方法：
将大区间的美味度指向小区间，小区间指向小小区间，注意每个相同的区间是一个点，不能累加多次，YY一下，发现就是一颗类似树的图，实现上，将每个di,j向di,j-1连边，再向di+1,j-1连边。然后每个di,i减去一个ai，然后同种的所有的di,i指向同一个m*ai*ai。然后，dinic一下，结果就过样例了!!!交了就A了。哇哈哈哈哈。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int ans,sum,n,m,s,t,a[110],d[110][110];
const int inf=0x3f3f3f3f;
bool v[1100];
int head[12000],to[100000],nxt[100000],f[100000],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=z;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
f[cnt]=0;
}
int dis[12000];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof(dis));
while(!q.empty()) q.pop();
q.push(s);dis[s]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx;f[i^1]+=xx;tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
s=n*n+n+1000+1; t=s+1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++) scanf("%d",&d[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++)
{
if(j!=1)
{
add(i*n+j,i*n+j-1,inf);
if(i!=n) add(i*n+j,(i+1)*n+j-1,inf);
}
else d[i][j]-=a[i];
if(d[i][j]>0) add(s,i*n+j,d[i][j]),sum+=d[i][j];
else add(i*n+j,t,-d[i][j]);
}
int c=n*n+n;
for(int i=1;i<=n;i++)
{
add(i*n+1,c+a[i],inf);
if(!v[a[i]]) v[a[i]]=1,add(c+a[i],t,m*a[i]*a[i]);
}
while(bfs()) ans+=dinic(s,inf);
printf("%d",sum-ans);
return 0;
}