前言
为毛我之前做网络流24题一篇题解都没有写
正片
例题
[六省联考2017]寿司餐厅
当时就想着用DP搞，结果死活搞不出那个m=1的做法
最大权闭合子图介绍
给你新的一道题目，有(n)个点，每个点有个(a)值，选了就会加上其(a)值，那么很明显加上全部正的(a)即可。
但是现在要求给你一些关系：选了(x)必须选(y)。
我们现在的(ans)先加上所有的正数。
那么，考虑最小割，如果在最小割中割了(x)和(S)的边，表示不选(x)，而割了(x)和(T)的边，然后需要注意的是，边权不是价值，而是代价，也就是需要从(ans)中减去的东西。（当然，倒过来应该也没有问题。）
对于一个点(i)，如果(a_i>0)，则向(S)连边权为(a_i)的边，向(T)连边权为(0)的边，如果(a_i≤0)，则向(S)连边权为(0)的边，向(T)连边权为(-a_i)的边。
好，那么如果选了(x)必须选(y)，就把(x)向(y)连一条边，边权为(∞)，为什么？
因为如果(x)选了，割了与(T)的边，(y)不选，割了与(S)的边，那么就一定存在一条路径：(S->x->y->T)。
所以(x)选了，(y)必须被选。
这就是最大权闭合子图。
做法
仔细一看，对于(d_{i,j})而言，选了其必须选择(d_{i+1,j},d_{i,j-1})，而对于(d_{i,i})而言，选了其必须删去(i)的代号，而对于(i)，如果其被选择，那么也要删去其代号的平方乘(m)。
然后跑Dinic即可。
代码
#include<cstdio>
#include<cstring>
#define N 110
#define NN 12000
#define M 110000
using namespace std;
inline int mymin(int x,int y){return x<y?x:y;}
struct node
{
int y,next,c;
}a[M];int len=1,last[NN];
inline void ins_node(int x,int y,int c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
inline void ins(int x,int y,int c){ins_node(x,y,c);ins_node(y,x,0);}
int list[NN],head,tail,h[NN],st,ed;
bool bfs()
{
memset(h,0,sizeof(h));h[ed]=1;
head=1;tail=1;list[1]=ed;
while(head<=tail)
{
int x=list[head++];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k^1].c && !h[y])
{
h[y]=h[x]+1;
list[++tail]=y;
}
}
}
return h[st];
}
int dinic(int x,int f)
{
if(x==ed)return f;
int s=0,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c && h[x]==h[y]+1)
{
s+=t=dinic(y,mymin(f-s,a[k].c));
a[k].c-=t;a[k^1].c+=t;
if(s==f)return s;
}
}
h[x]=0;
return s;
}
bool v[1100];
int ans=0;
inline void jian(int x,int v)
{
if(v>0)
{
ans+=v;
ins(st,x,v);
}
else if(v<0)ins(x,ed,-v);
}
int n,m,d[N][N];
int main()
{
scanf("%d%d",&n,&m);
st=n*n+n+1000+1;ed=st+1;
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
if(!v[x] && m)jian(n*n+x,-m*x*x),v[x]=1;
jian(n*n+1000+i,-x);
ins(n*n+1000+i,n*n+x,999999999);
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
scanf("%d",&d[i][j]);
jian((i-1)*n+j,d[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(i==j)ins((i-1)*n+j,n*n+1000+i,999999999);
else ins((i-1)*n+j,i*n+j,999999999),ins((i-1)*n+j,(i-1)*n+j-1,999999999);
}
}
while(bfs())
{
ans-=dinic(st,999999999);
}
printf("%d
",ans);
return 0;
}
/*
1-n^2表示d(i,j)
n^2+1-n^2+1000表示第i个代号。
n^2+1001-n^2+1000+n表示第i个数字，减去其代号
*/