[BZOJ4873][六省联考2017]寿司餐厅(最大权闭合子图)

挺简单的最大权闭合子图模型，我怎么就没有看出来呢？

首先将d[][]看成一个右上三角矩阵，那么如果d[i][j]有贡献，那么d[i+1][j]和d[i][j-1]都必然有贡献。

考虑付费情况，每个位置建一个点i'，d[i][j]向i'和j'连边，i'，j' 向T连各自费用的边。对于$mx^2$的部分，对每个编号再建一个新点bel，i'向bel[a[i]]连边。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rep(i,l,r) for (int i=l; i<=r; i++)

#define For(i,x) for (int i=h[x],k; i; i=nxt[i])

using namespace std;

const int N=30100,M=2000100,inf=0x3f3f3f3f;

int to[M],nxt[M],f[M],h[N],q[M],d[N],mp[110][110],id[110][110],bel[1010];

int n,m,S,T,ans,cnt=1,tot,a[N],vis[1010];

void add(int u,int v,int w){

    to[++cnt]=v; nxt[cnt]=h[u]; f[cnt]=w; h[u]=cnt;

    to[++cnt]=u; nxt[cnt]=h[v]; f[cnt]=0; h[v]=cnt;

}

bool bfs(){

    memset(d,0,sizeof(d)); q[1]=S; d[S]=1;

    for (int st=0,ed=1; st!=ed; ){

        int x=q[++st];

        For(i,x) if (!d[k=to[i]] && f[i])

            d[k]=d[x]+1,q[++ed]=k;

    }

    return d[T];

}

int dfs(int x,int lim){

    if (x==T) return lim;

    int c=0;

    For(i,x) if (f[i] && d[k=to[i]]==d[x]+1){

        int t=dfs(k,min(f[i],lim-c));

        c+=t; f[i]-=t; f[i^1]+=t;

        if (c==lim) return lim;

    }

    if (!c) d[x]=-1;

    return c;

}

int dinic(){ int res=0; while (bfs()) res+=dfs(S,inf); return res;}

void build(){

    S=0;

    rep(i,1,n) rep(j,i,n) id[i][j]=++tot;

    rep(i,1,n) if (!vis[a[i]]) vis[a[i]]=1,bel[a[i]]=++tot;

    T=tot+n+1;

    memset(vis,0,sizeof(vis));

    rep(i,1,n) if (!vis[a[i]]) vis[a[i]]=1,add(bel[a[i]],T,m*a[i]*a[i]);

    rep(i,1,n) add(tot+i,bel[a[i]],inf),add(tot+i,T,a[i]);

    rep(i,1,n) rep(j,i,n){

        add(id[i][j],tot+i,inf),add(id[i][j],tot+j,inf);

        if (mp[i][j]>0) ans+=mp[i][j],add(S,id[i][j],mp[i][j]);

            else if (mp[i][j]<0) add(id[i][j],T,-mp[i][j]);

        if (i!=j) add(id[i][j],id[i+1][j],inf),add(id[i][j],id[i][j-1],inf);

    }

}

int main(){

    freopen("sushi.in","r",stdin);

    freopen("sushi.out","w",stdout);

    scanf("%d%d",&n,&m);

    rep(i,1,n) scanf("%d",&a[i]);

    rep(i,1,n) rep(j,i,n) scanf("%d",&mp[i][j]);

    build(); printf("%d\n",ans-dinic());

    return 0;

}