P3749 [六省联考 2017] 寿司餐厅 题解
发现很少有人讲为什么这题是最大权闭合子图，但作为一个刚学网络流的蒟蒻，我认为考虑是必要的。
最大权闭合子图的特点：
- 存在单向依赖关系，选 \(x\) 必须选 \(y\)。
- 每个点只会被选一次。
- 代价有正有负。
本问题特点：
- 选一个区间，必选所有子区间（单向依赖）。
- 贡献 & 代价都只算一次。
- 有正有负。
完美符合要求！
只需要打个补丁，选 \([i,i]\) 必选 \(a_i\)。
会最大权闭合子图的可以跳过下面一部分。
最大权闭合子图模型
考虑最优为选所有正的，不选负的。
建图：
- \(s\) 为源点，\(t\) 为汇点。
- 对于依赖关系 \(x\to y\)，连边 \((x,y,INF)\)。
- 对于节点，若代价为正，连边 \((s,i,v_i)\)；反之，连边 \((i,t,-v_i)\)。
若割掉与 \(s\) 相连的边，代表不选这个正的，损失 \(v_i\) 贡献；若割掉与 \(t\) 相连的边，代表选这个负的，付出 \(v_i\) 代价。
发现 \(s\) 和 \(t\) 只会通过形如 \(s\to x\to y\to t\) 的边相连。
- 如果保留 \((y,t)\)，即选 \(y\)，则必然割掉 \((s,x)\)，即不选 \(x\)。
- 如果割掉 \((y,t)\)，即不选 \(y\)，\((s,x)\) 可割可不割，不受影响。
故此图的割满足选 \(y\) 是选 \(x\) 的必要条件。
最大权为 所有正权值之和 \(-\) 最小割。
讲到这里本题建图就很简单了，不懂的请自行看代码理解。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define REPG(i,g,x) for(int i=g.head[x];~i;i=g.edge[i].nxt)
//此处省略快读板子
const int N=1e5+5,M=2e6+5;
struct graph{
int head[N],cnt;
struct node{
int to,nxt,w,c;
}edge[M];
inline void add(int x,int y,int w,int c){
edge[++cnt]=(node){y,head[x],w,c};head[x]=cnt;
}
inline void clear(){
memset(head,-1,sizeof(head));cnt=1;
}
}g;
int n,m,s,t;
const int NF=105;
const int INF=1e9+5;
int a[NF],d[NF][NF],id[NF][NF];
int Maxa;
namespace Dinic{
int dep[N],cur[N];
queue<int> q;
bool bfs(){
memset(dep,-1,sizeof(dep));
memcpy(cur,g.head,sizeof(g.head));
while(!q.empty()) q.pop();
dep[s]=1;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
if(u==t) break;
REPG(i,g,u){
int v=g.edge[i].to,w=g.edge[i].w,c=g.edge[i].c;
if(dep[v]==-1 && w>c){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]!=-1;
}
int dfs(int u,int f){
if(u==t || !f) return f;
int res=0;
for(int i=cur[u];(~i) && f!=res;i=g.edge[i].nxt){
int v=g.edge[i].to,w=g.edge[i].w,c=g.edge[i].c;
cur[u]=i;
if(dep[v]==dep[u]+1 && w>c){
int nf=dfs(v,min(f-res,w-c));
res+=nf;
g.edge[i].c+=nf;
g.edge[i^1].c-=nf;
}
}
return res;
}
int solve(){
int ans=0;
while(bfs()) ans+=dfs(s,INF);
return ans;
}
}
int main(){
g.clear();
read(n),read(m);
rep(i,1,n) read(a[i]),Maxa=max(Maxa,a[i]);
s=1,t=2;
int tot=2;
rep(i,1,n) rep(j,i,n){
read(d[i][j]);
id[i][j]=++tot;
}
int mx=0;
rep(i,1,n) rep(j,i,n){
if(i==j){
//选 d[i][i] 必选 a[i]
g.add(id[i][j],tot+a[i],INF,0);
g.add(tot+a[i],id[i][j],0,0);
//选 d[i][i] 需要付出 a[i] 的代价
d[i][j]-=a[i];
}
else{
//选 d[i][j] 必选 d[i+1][j],d[i][j-1]
g.add(id[i][j],id[i+1][j],INF,0);
g.add(id[i+1][j],id[i][j],0,0);
g.add(id[i][j],id[i][j-1],INF,0);
g.add(id[i][j-1],id[i][j],0,0);
}
if(d[i][j]>0) g.add(s,id[i][j],d[i][j],0),g.add(id[i][j],s,0,0),mx+=d[i][j];
else g.add(id[i][j],t,-d[i][j],0),g.add(t,id[i][j],0,0);
}
//选 i 需要付出 m*i*i 的代价
rep(i,1,Maxa) g.add(tot+i,t,m*i*i,0),g.add(t,tot+i,0,0);
printf("%d\n",mx-Dinic::solve());
return 0;
}