【BZOJ4873】寿司餐厅（六省联考2017）-最小割

测试地址：寿司餐厅
做法：本题需要用到最小割。
首先，仔细看题，计算价钱中的 $c$ 是种数而不是个数，那么我们发现每种贡献都仅会被计算一次，考虑把这些东西建成点，于是就变成了选点问题。
我们发现有以下一些限制条件：
1.如果要选区间 $[l, r]$ ，必须同时选区间 $[l, r - 1]$ 和 $[l + 1, r]$ 。
2.如果要选第 $i$ 种寿司，那么同时会产生 $a_{i}$ 的费用。
3.如果代号为 $i$ 的寿司被选中过一次以上，会产生 $m i^{2}$ 的费用。
那么我们把区间建成点，点权为选它对答案产生的贡献，在计算 $[i, i]$ 这种区间的贡献时，可以把上面第2条的费用算进去，不然另建出一个点也可以。由于同种代号的寿司的第3条贡献只会被计算一次，因此我们还要对所有代号建出点，点权为 $- m i^{2}$ ，当我们选 $[i, i]$ 时，必然要选代号为 $a_{i}$ 的点。我们发现这就变成了一个最大权闭合子图的问题，是经典的最小割应用，建模后跑一遍最大流即可。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(ll)1000000000*(ll)1000000000;
int n,m,S,T,a[110],id[110][110],totid=0;
int first[10010]={0},tot=1,h,t,q[10010],lvl[10010],cur[10010];
ll sum=0;
struct edge
{
    int v,next;
    ll f;
}e[100010];

void insert(int a,int b,ll f)
{
    e[++tot].v=b,e[tot].next=first[a],e[tot].f=f,first[a]=tot;
    e[++tot].v=a,e[tot].next=first[b],e[tot].f=0,first[b]=tot;
}

void init()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            id[i][j]=++totid;
    S=totid+1001+1,T=totid+1001+2;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            ll val;
            scanf("%lld",&val);
            if (j>i)
            {
                if (val<0) insert(id[i][j],T,-val);
                else sum+=val,insert(S,id[i][j],val);
                insert(id[i][j],id[i][j-1],inf);
                insert(id[i][j],id[i+1][j],inf);
            }
            else
            {
                val-=(ll)a[i];
                if (val<0) insert(id[i][i],T,-val);
                else sum+=val,insert(S,id[i][i],val);
                insert(id[i][i],totid+a[i]+1,inf);
            }
        }
    for(int i=0;i<=1000;i++)
        insert(totid+i+1,T,m*(ll)i*(ll)i);
}

bool makelevel()
{
    for(int i=1;i<=totid;i++)
        lvl[i]=-1,cur[i]=first[i];
    for(int i=1;i<=n;i++)
    {
        lvl[totid+a[i]+1]=-1;
        cur[totid+a[i]+1]=first[totid+a[i]+1];
    }
    lvl[S]=0;cur[S]=first[S];
    lvl[T]=-1;
    h=t=1;
    q[1]=S;
    while(h<=t)
    {
        int v=q[h++];
        for(int i=first[v];i;i=e[i].next)
            if (e[i].f&&lvl[e[i].v]==-1)
            {
                lvl[e[i].v]=lvl[v]+1;
                q[++t]=e[i].v;
            }
    }
    return lvl[T]!=-1;
}

ll maxflow(int v,ll maxf)
{
    ll ret=0,f;
    if (v==T) return maxf;
    for(int i=cur[v];i;i=e[i].next)
    {
        if (e[i].f&&lvl[e[i].v]==lvl[v]+1)
        {
            f=maxflow(e[i].v,min(maxf-ret,e[i].f));
            ret+=f;
            e[i].f-=f;
            e[i^1].f+=f;
            if (ret==maxf) break;
        }
        cur[v]=i;
    }
    if (!ret) lvl[v]=-1;
    return ret;
}

void dinic()
{
    ll maxf=0;
    while(makelevel()) maxf+=maxflow(S,inf);
    printf("%lld",sum-maxf);
}

int main()
{
    init();
    dinic();

    return 0;
}