BZOJ:4873: [Shoi2017]寿司餐厅

4873: [Shoi2017]寿司餐厅

首先很开心在膜你赛的时候做了出来。

看到数据范围，看到不能dp，看到贡献去重后计算，咦，流？

那就容易了，转最大权闭合子图，每个区间建一个点，取了就一定要取他的子区间（依赖关系），代价上也很容易用依赖关系搞。

提交完A了就没理，后来同学说我#1了？？？

#include<cstdio>

#include<algorithm>

#define MN 40001

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

const int INF=1e9;

struct na{int y,z,ne;}b[MN*];

int n,m,map[][],nu[][],a[],num=,no=,S,T,mmh=,g[MN],c[MN],d[MN],l[MN];

inline void in(int x,int y,int z){b[++num].y=y;b[num].z=z;b[num].ne=l[x];l[x]=num;}

inline void add(int x,int y,int z){in(x,y,z);in(y,x,);}

inline int min(int a,int b){return a<b?a:b;}

int sap(int x,int f){

    if (x==T) return f;

    int h=,q;

    for (int i=d[x];i;i=b[i].ne)

    if (b[i].z&&g[b[i].y]+==g[x]){

        q=sap(b[i].y,min(b[i].z,f-h));

        h+=q;b[i].z-=q;b[i^].z+=q;

        if (h==f||g[S]==no) return h;

    }

    if (!(--c[g[x]])) g[S]=no;d[x]=l[x];c[++g[x]]++;

    return h;

}

int main(){

    register int i,j;

    n=read();m=read();

    S=++no;T=++no;

    for (i=;i<=n;i++)

    for (j=i;j<=n;j++) nu[i][j]=++no;

    for (i=;i<=n;i++)

    for (j=i+;j<=n;j++)

    add(nu[i][j],nu[i][j-],INF),add(nu[i][j],nu[i+][j],INF);

    for (i=;i<=n;i++){

        a[i]=read();map[i][i]-=a[i];

        add(nu[i][i],no+a[i],INF);

    }

    for (i=;i<=n;i++)

    for (j=i;j<=n;j++) if ((map[i][j]+=read())>) add(S,nu[i][j],map[i][j]),mmh+=map[i][j];else add(nu[i][j],T,-map[i][j]);

    if (m) for (i=;i<=;i++) add(no+i,T,i*i);no+=;

    for (;g[S]<no;mmh-=sap(S,INF));

    printf("%d\n",mmh);

}