最大权闭合子图

闭合子图

定义有向图的一个闭合子图是该有向图的一个点集，其中这个点集中的所有点的出边连向的还是点集中的点。

最大权闭合子图

给有向图的点加一个点权，能得到的点权最大的闭合子图。

网络流模型

将所有正点权的点的点权全部加入答案。接下来我们将原来正点权的点变成负点权。现在图上全是负点，我们需要尽量选最少点权使图符合条件。
设超级源点和超级汇点。
将超级源向所有原来是正点权的点连边，流量为其点权绝对值。
将所有负点权的点向超级汇连边，流量为其点权绝对值。
将所有原图上的边加入，流量为无限。
接下来跑最小割。可以证明此时最小割就是使图合法的最小代价。感性理解一下，将源点与汇点割开的最小割，因为原图的边的流量是无限，只能将超级源汇连出去的边割开。相当于就是不选某些正点或选择某些汇点。这也就保证了后面的点选择时前面的点一定会被选。
最后用前面的答案减去最小割即可。
如果需要构造方案，请看下例题。

P2762 太空飞行计划问题

题意

给你两个集合，一个集合所有元素有正点权，另一个有负点权，前一个集合的每一个元素有若干后一个集合的必选后继，要求若选择该元素后继必选，求能得到的最大点权和。

思路

最大权闭合子图模板。将前一个集合的所有元素向其所有后继连边，就变成了一个有向图，然后用上述方法建模即可。

关于读入

我使用了快读来读入换行符。其代码如下：

inline int read(){
    int w=0,x=0;static char c(0);
    while(!isdigit(c) and c!='\n') w|=c=='-',c=getchar();
    if(c=='\n')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!='\n') w|=c=='-',c=getchar();
		if(c=='\n')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("\n%d\n",ans);
	}
}
signed main(){
	star::work();
	return 0;
}

CF103E Buying Sets

题意

有一个大小为 n 的全集，每个元素是一个数，有 n 个子集。题目保证任意 k 个子集的并的大小 ⩾ k。

每个子集有一个可正可负的权值，你需要选出一些子集使得这些子集并的大小等于子集个数，且所选子集的权值和最小。可以为空集。

思路

发现如果没有 子集并的大小等于子集个数 的限制，将边权取负就是最大权闭合子图的模板。考虑怎么满足这个限制。

我们把每个节点的点权加上一个巨大的偏移量 \(\Delta\) 即可。

原因是，如果跑最大流时要多选一个点的话，代价一定会变得很大。因为题目保证 任意 k 个子集的并的大小 ⩾ k，而且可以选空集，所以我们可以这么干。

早期代码