最大权闭合子图
闭合子图
定义有向图的一个闭合子图是该有向图的一个点集，其中这个点集中的所有点的出边连向的还是点集中的点。
最大权闭合子图
给有向图的点加一个点权，能得到的点权最大的闭合子图。
网络流模型
- 将所有正点权的点的点权全部加入答案。接下来我们将原来正点权的点变成负点权。现在图上全是负点，我们需要尽量选最少点权使图符合条件。
- 设超级源点和超级汇点。
- 将超级源向所有原来是正点权的点连边，流量为其点权绝对值。
- 将所有负点权的点向超级汇连边，流量为其点权绝对值。
- 将所有原图上的边加入，流量为无限。
- 接下来跑最小割。可以证明此时最小割就是使图合法的最小代价。感性理解一下，将源点与汇点割开的最小割，因为原图的边的流量是无限，只能将超级源汇连出去的边割开。相当于就是不选某些正点或选择某些汇点。这也就保证了后面的点选择时前面的点一定会被选。
- 最后用前面的答案减去最小割即可。
- 如果需要构造方案，请看下例题。
P2762 太空飞行计划问题
题意
给你两个集合，一个集合所有元素有正点权，另一个有负点权，前一个集合的每一个元素有若干后一个集合的必选后继，要求若选择该元素后继必选，求能得到的最大点权和。
思路
最大权闭合子图模板。将前一个集合的所有元素向其所有后继连边，就变成了一个有向图，然后用上述方法建模即可。
关于读入
我使用了快读来读入换行符。其代码如下：
inline int read(){
int w=0,x=0;static char c(0);
while(!isdigit(c) and c!='
') w|=c=='-',c=getchar();
if(c=='
')return c=getchar(),INF;
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
其中，利用了 static 来保证之前读入的字符能够重新判断。在这个函数中，如果读到换行符将会返回 INF。
关于输出方案
在这道题中，思考网络流建模方式即可得出，如果在最后一次 bfs 中一个正点权的点可以到达，说明其没有被取消选择，即被选择了；如果一个负点权的点可以到达，说明其被选择了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
namespace star
{
const int maxn=105,maxm=2600,s=103,t=104,INF=0x3f3f3f3f;
inline int read(){
int w=0,x=0;static char c(0);
while(!isdigit(c) and c!='
') w|=c=='-',c=getchar();
if(c=='
')return c=getchar(),INF;
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
int n,m,val[maxn],ans;
int ecnt=1,head[maxn],cur[maxn],to[maxm<<1],nxt[maxm<<1],w[maxm<<1];
inline void addedge(int a,int b,int c){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt,w[ecnt]=c;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt,w[ecnt]=0;
}
int dep[maxn];
inline bool bfs(){
memset(dep,-1,sizeof dep);
static int q[maxn];
int hd=0,tl=1;
q[tl]=s,dep[s]=0;
while(hd<tl){
int x=q[++hd];
for(int u,i=head[x];i;i=nxt[i]) if(dep[u=to[i]]==-1 and w[i])
dep[u]=dep[x]+1,q[++tl]=u;
}
return dep[t]!=-1;
}
int dfs(int x,int flow){
if(x==t)return flow;
int used=0,u;
for(int& i=cur[x];i;i=nxt[i]) if(dep[u=to[i]]==dep[x]+1 and w[i]){
int v=dfs(u,min(flow-used,w[i]));
used+=v,w[i]-=v,w[i^1]+=v;
if(used==flow) break;
}
return used;
}
inline int dinic(){
int ans=0;
while(bfs()) memcpy(cur,head,sizeof cur),ans+=dfs(s,INF);
return ans;
}
inline void work(){
m=read(),n=read();read();
for(int v,i=1;i<=m;i++){
addedge(s,i,v=read());ans+=v;
while((v=read())!=INF) addedge(i,v+m,INF);
}
for(int i=1;i<=n;i++) addedge(i+m,t,read());
ans-=dinic();
for(int i=1;i<=m;i++) if(dep[i]!=-1) printf("%d ",i);puts("");
for(int i=1;i<=n;i++) if(dep[m+i]!=-1) printf("%d ",i);
printf("
%d
",ans);
}
}
signed main(){
star::work();
return 0;
}
CF103E Buying Sets
题意
有一个大小为 n 的全集，每个元素是一个数，有 n 个子集。题目保证任意 k 个子集的并的大小 ⩾ k。
每个子集有一个可正可负的权值，你需要选出一些子集使得这些子集并的大小等于子集个数，且所选子集的权值和最小。可以为空集。
思路
发现如果没有 子集并的大小等于子集个数 的限制，将边权取负就是最大权闭合子图的模板。考虑怎么满足这个限制。
我们把每个节点的点权加上一个巨大的偏移量 (Delta) 即可。
原因是，如果跑最大流时要多选一个点的话，代价一定会变得很大。因为题目保证 任意 k 个子集的并的大小 ⩾ k，而且可以选空集，所以我们可以这么干。