网络流24题

顺序主观决定

太空飞行计划

教训：(开始想费用流，搞半天出不来)

网络流解决最大/小费用问题，要么最小割最大流，要么最小费用流

最小费用流的前提是最大流，所以在有一些点可以不取换最优代价的时候，是不可行的。

当每个点都只能取一次的时候，可以考虑费用化为容量，求最小割/最大流。

回到这个题，假如我们把一个实验所需器材用有向边连起来，问题就化为了：

在一个二分图中，左部点向右部点有若干连边，若选择了某一个左部点，则所连右部点必选。求最后最大的点权和

将其转化为有向图，问题化为：

在一张有向图中，选出一个子图，满足选择了一个点，它的后继所有点都必选，求最大和

最大权闭合子图模型

这个模型是用来解决上述问题的。

定理：若将源点与所有正权点连边，容量为点权，汇点与所有负权点连边，容量为点权的相反数，同时保留原有向图所有边，容量正无穷，则正权点的点权和减去最小割即为所求。

证明

被割掉的边的意义：

1. 边 \((s,u,w[u])\) 被割，表示不选 \(u\)
2. 边 \((v,t,w[v])\) 被割，表示选 \(v\)

这样就可以求出最大权闭合子图的点集，进而求出图 \(G'\)

引理：Dinic 算法最后一次分层(failed)的 \(dep\) 数组就可以用来判断可达性。可达的点构成了最大权闭合子图。

由此，我们可以由源点向每个实验连边，容量为收益，由汇点向每个器材连边，容量为代价。由每个实验向所需器材连边，容量正无穷。

若某实验没被割，则加入答案。若某器材被割，则加入答案。

    read(m);read(n);int ans=0;s=n+m+1,t=n+m+2;num=t; 
	for(int i=1;i<=m;i++){
		int y;
		int x=read(y);
		add(s,i,y);ans+=y;
		while(!x){
			int y;x=read(y);
			add(i,m+y,inf);
		}
	}//鬼畜输入
	for(int i=1;i<=n;i++){
		int x;read(x);add(m+i,t,x); 
	}
	ans-=dinic();
	for(int i=1;i<=m;i++)if(dep[i])cout<<i<<" ";
	cout<<"\n";
	for(int i=m+1;i<=n+m;i++)if(dep[i])cout<<i-m<<" ";cout<<"\n";
	cout<<ans<<"\n";

最小路径覆盖问题

给定一个DAG，求其最小路径覆盖。

这里体现的重要思想有两个：

1. 将一个点的不同状态拆分，化为左右部，分别求解
2. 部分计算，合并答案
3. 正难则反，拆分——>合并

首先，我们将在DAG里拆路径的过程倒过来，变为合并路径。最初将 \(n\) 个点都单独是做一条路径。

然后我们考虑合并路径的操作。要路径条数最少，则合并次数最多。

注意到有向图中，每个点有两个状态：作为该边的入点，作为该边的出点。而在路径合并中，显然要区分开这两种状态，只能入状态向出状态合并。

为什么？我们需要的是合并次数，而非正常建图的流量。求最大流，也即最大化流量，而现在我们要最大化合并次数，所以合并次数就是我们的流量，而合并次数为了判重(一个点最多给1次)，必须一对对拆。

显然原图一条边最多提供1次合并，那么对于原图的每一条边，由入状态向出状态的另一端点连边，容量1，表示提供1的合并次数。

那么对于入状态的点，可以找一个点合并，则由源点向其连边，容量1

对于出状态的点，可以被一个点合并，则由其向汇点连边，容量1

综上，我们将一个点拆为 \(i,i+n\)，建立边 \((s,i,1),(i+n,t,1),(u,v+n,1)\)跑最大流，即可得到最大合并次数。

用总点数减去最大合并次数即可得到最小路径数。

关于方案输出？网络流的方案输出一般体现在满流边和残量网络上，当然也可以像动态规划一样记录上一个点。

这里常用的方法是由汇点开始找残量网络，找到的路径就对应了合并关系。

但更简单的方法？注意到原图里边的容量全是1，那么就必有 \(lst\) 唯一，在网络流DFS过程中直接记录 \(lst\)，倒回来输出即可。

请注意，这里还没完，我们只得到了若干对合并关系，但不能就此输出整个路径。我们可以通过合并关系确定每个点在合并后路径上的 \(lst\)，然后根据路径终点直接跳就好(终点判断：标记是否被记录过作为合并的主动方)

vector<int>f[N];int dcc; 
int vis[N],suf[N];
void init(){
	cin>>n>>m;s=n+n+1,t=n+n+2;num=t;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;add(u,v+n,1);
	}
	for(int i=1;i<=n;i++)add(s,i,1);
	for(int i=n+1;i<=n<<1;i++)add(i,t,1);
	int ans=dinic();
	for(int i=head[t];i;i=nxt[i]){
		if(cost[i]==1){
			++dcc;int x=ver[i];
			while(x!=s){
				f[dcc].push_back(x),x=lst[x];
			}
			if(f[dcc][1]>n)f[dcc][1]-=n;
			if(f[dcc][0]>n)f[dcc][0]-=n;
			suf[f[dcc][1]]=f[dcc][0];vis[f[dcc][0]]=1;
		}
	} 
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int x=i;
			while(x){
				cout<<x<<" ";x=suf[x];
			}cout<<"\n";
		}
	}
	cout<<n-ans<<"\n";
}

下面来看一个同为网络流24题的变形题。

魔术球问题

一个显然的结论是：柱子越多，可以投入的数越大，我们可以考虑逐步增大答案。

注意到我们如果将两个和为完全平方数的数连边，限制大连小，那么一个石柱其实就对应了这样一张DAG的简单路径。问题化为求该DAG的最小路径覆盖。当这个路径覆盖数超过 \(k\) 说明上一个枚举的数即为答案，此时重新建图，跑一边最小路径覆盖，合并路径后直接输出即可。注意输出顺序。

vector<int>f[N];int dcc,ans; 
void dinic(){
	while(bfs()){
		for(int i=1;i<=num;i++)cur[i]=head[i];
		ans+=dfs(s,0x3f3f3f3f);
	}
//	cout<<ans<<"\n";
}
int vis[N],suf[N];
void init(){
	cin>>n;
	s=1,t=2;int d=0;
	for(int i=1;;i++){
		int x=i*2+1,y=(i+1)*2;
		add(s,x,1);add(y,t,1);
		for(int j=1;j<i;j++){
			int q=sqrt(i+j);if(i+j==q*q){
				add(x,(j+1)*2,1);
			}
		}
		num=y;
		dinic();
		if(i-ans==n+1){
			cout<<i-1<<"\n";d=i-1;break;
		}
	}
	for(int i=1;i<=num;i++)head[i]=0;tot=1;
	for(int i=1;i<=d;i++){
		int x=i*2+1,y=(i+1)*2;
		add(s,x,1);add(y,t,1);
		for(int j=1;j<i;j++){
			int q=sqrt(i+j);if(i+j==q*q){
				add(x,(j+1)*2,1);
			}
		}
	}
	num=d*2+2;
	dinic();
	for(int i=head[t];i;i=nxt[i]){
		if(cost[i]==1){
			++dcc;int x=ver[i];
			while(x!=s){
				f[dcc].push_back(x),x=lst[x];
			}
			f[dcc][0]=f[dcc][0]/2-1;
			f[dcc][1]/=2;
			suf[f[dcc][0]]=f[dcc][1];vis[f[dcc][1]]=1;
		}
	} 
	for(int i=1;i<=d;i++){
		if(!vis[i]){
			int x=i;
			while(x){
				cout<<x<<" ";vis[x]=1;x=suf[x];
			}cout<<"\n";
		}
	}
}

最长 k 可重区间集问题

题意：给定若干 开区间，求选出一个区间集 \(S\)，使得其选出的区间长度和最大且不存在一个点被覆盖了 \(k\) 次以上。

真的是非常巧妙的问题！

首先，虽然这是个区间操作问题，我们仍然可以将其抽象为(亦或者说微观化？)序列元素操作问题。我们将区间端点离散化后，这题就变成了：选出若干区间，使得每个点覆盖次数小于等于 \(k\)，这里的覆盖变成了严格的 \(l<x<r\)。开区间嘛。

我们需要解决的问题有两个：

1. 如何表示区间覆盖
2. 如何表示一个点的覆盖次数

注意到我们要求的是最大长度为区间长度和，而非覆盖范围。每一个点必定在最后都是合法的，而我们解决问题的基本元素就是点，则最终网络满流，所以这个长度和必定是一个费用，本题为最大费用最大流问题。

那么用费用表示区间长度，则只能用流量表示覆盖次数了。如果我们设经过一个点的流量表示这个点的覆盖次数，可以吗？发现难以维护区间被覆盖的问题，本质原因是在流网络中，加边的后果就是导致分流。分流有两种情况，一是从源点引流，增加该边以后的流量，而是从其他点分流，使得经过其他点的流量减少，而我们影响的对象是该区间内的点，只能选择分流该区间的流量。此时就是本题做法的最精妙之处了：设经过一个点的流量表示其还能被覆盖几次。正难则反的思想是处处可见呢！

有了这个状态定义，整个问题就变得容易了起来。状态的定义是解决问题的大前提，类似于战略

我们为了限制一个点的被覆盖次数最多 \(k\) 次，显然必须要连边 \((i,i+1,k,0)\)，其中分别表示出点，入点，容量，费用。这限制了通过一个点的流量最多为 \(k\)。

那么我们考虑使得通过一个点的流量减少1，则有一条容量为1的，费用更优的边在旁边分流。故建立 \((l,r,1,len)\)。

有最大流的限制，使得求该网络的最大费用即为所求。

回顾整个题，不难发现闪烁思想光芒的点主要有三个：

1. 问题转化——将区间选择更换角度为点的选择
2. 状态定义——运用推理的方法，找到最优的状态
3. 最大流性质—利用所有点必选的最大流限制，来限制区间选择

在这里提一句，在费用流问题中，流量是第一关键字，费用只是第二关键字。一般我们用费用流求最优化问题时，都有所有状态必选的性质。

星际转移问题

结合时间轴的网络流问题。