一道神奇的网络流题目。
建议先做关于最大权闭合子图的题。
比如bzoj1497
#include<bits/stdc++.h> #define LL long long #define N 5003 #define M 500003 #define INF 2100000000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void print(int x) { if(x<0){putchar('-');x=-x;} if(x>9)print(x/10); putchar(x%10+'0'); } struct EDGE{ int nextt,to,val; }w[4*M+2*N]; int head[M+N],d[M+N],cur[M+N]; int tot=1,S,T; void add(int a,int b,int c) { tot++; w[tot].nextt=head[a]; w[tot].to=b; w[tot].val=c; head[a]=tot; } queue<int>q; bool bfs() { memset(d,0,sizeof(d)); while(q.size())q.pop(); q.push(S);d[S]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(!d[v]&&w[i].val) { q.push(v); d[v]=d[x]+1; if(v==T)return 1; } } } return 0; } int dinic(int x,int flow) { if(x==T)return flow; int rest=0; //for(int i=head[x];i;i=w[i].nextt) for(int &i=cur[x];i;i=w[i].nextt) { int v=w[i].to; if(w[i].val&&d[v]==d[x]+1) { int k=dinic(v,min(flow-rest,w[i].val)); rest+=k; w[i].val-=k;w[i^1].val+=k; if(rest==flow)return rest; } } return rest; } int main() { int n=read(),m=read(); S=0,T=n+m+1; for(int i=1;i<=n;++i) { int a=read(); add(i,T,a);add(T,i,0); } int sum=0; for(int i=1;i<=m;++i) { int a=read(),b=read(),c=read(); sum+=c; add(i+n,a,INF);add(a,i+n,0); add(i+n,b,INF);add(b,i+n,0); add(S,i+n,c);add(i+n,S,0); } int flow=0,maxflow=0; while(bfs()) { for(int i=S;i<=T;++i) cur[i]=head[i]; while(flow=dinic(S,INF))maxflow+=flow; } printf("%d\n",sum-maxflow); } /* */
然后这道题是一道也是最大权闭合子图的题。（还真没看出来）
然后就是神奇的建图连边。
如果是正的美味程度，向S连边。如果是负的美味程度，向T连边。
花费为mx*x+cx，考虑将两者分开看。
mx^2直接向T连边。
cx因为和选到的个数有关，这里有一个小处理，把每一个寿司美味程度减去一个对应的x（因为选了这个寿司一定会造成x的花费）。
然后因为如果选了[i，j]就一定要选[i，j-1]和[i+1，j]，所以[i，j]向[i，j-1]和[i+1，j]连边，权值为INF。
最后结果就是正权值之和-最小割。
#include<bits/stdc++.h> #define LL long long #define N 20003 #define M 200003 #define INF 2100000000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void print(int x) { if(x<0){putchar('-');x=-x;} if(x>9)print(x/10); putchar(x%10+'0'); } struct EDGE{ int nextt,to,val; }w[M*2]; int tot=1; int head[N],d[N],cur[N],a[N],ord[N],vis[N],g[102][102],dil[102][102]; void add(int a,int b,int c) { tot++; w[tot].nextt=head[a]; w[tot].to=b; w[tot].val=c; head[a]=tot; tot++; w[tot].nextt=head[b]; w[tot].to=a; w[tot].val=0; head[b]=tot; } int ndnum=0,S,T; queue<int>q; bool bfs() { memset(d,0,sizeof(d)); while(q.size())q.pop(); q.push(S);d[S]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(!d[v]&&w[i].val) { q.push(v); d[v]=d[x]+1; if(v==T)return 1; } } } return 0; } int dinic(int x,int flow) { if(x==T)return flow; int rest=0; //for(int i=head[x];i;i=w[i].nextt) for(int &i=cur[x];i;i=w[i].nextt) { int v=w[i].to; if(w[i].val&&d[v]==d[x]+1) { int k=dinic(v,min(flow-rest,w[i].val)); rest+=k; w[i].val-=k;w[i^1].val+=k; if(rest==flow)return rest; } } return rest; } int main() { // freopen("sushi.in","r",stdin); // freopen("sushi.out","w",stdout); int n=read(),m=read(); int maxx=0; for(int i=1;i<=n;++i) { a[i]=read(); maxx=max(maxx,a[i]); } for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) dil[i][j]=read(),g[i][j]=++ndnum; S=0;T=ndnum+maxx+1; int sum=0; for(int i=1;i<=maxx;++i)add(ndnum+i,T,m*i*i); for(int i=1;i<=n;++i)add(g[i][i],a[i]+ndnum,INF),dil[i][i]-=a[i]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(dil[i][j]>0)add(S,g[i][j],dil[i][j]),sum+=dil[i][j]; if(dil[i][j]<0)add(g[i][j],T,-dil[i][j]); if(j>i)add(g[i][j],g[i][j-1],INF),add(g[i][j],g[i+1][j],INF); } int flow=0,maxflow=0; while(bfs()) { for(int i=S;i<=T;++i) cur[i]=head[i]; while(flow=dinic(S,INF))maxflow+=flow; } printf("%d\n",sum-maxflow); }