网络流24题
顺序主观决定
太空飞行计划
教训：(开始想费用流，搞半天出不来)
网络流解决最大/小费用问题，要么最小割最大流，要么最小费用流
最小费用流的前提是最大流，所以在有一些点可以不取换最优代价的时候，是不可行的。
当每个点都只能取一次的时候，可以考虑费用化为容量，求最小割/最大流。
回到这个题，假如我们把一个实验所需器材用有向边连起来，问题就化为了：
在一个二分图中，左部点向右部点有若干连边，若选择了某一个左部点，则所连右部点必选。求最后最大的点权和
将其转化为有向图，问题化为：
在一张有向图中，选出一个子图，满足选择了一个点，它的后继所有点都必选，求最大和
最大权闭合子图模型
这个模型是用来解决上述问题的。
定理：若将源点与所有正权点连边，容量为点权，汇点与所有负权点连边，容量为点权的相反数，同时保留原有向图所有边，容量正无穷，则正权点的点权和减去最小割即为所求。
被割掉的边的意义：
- 边 \((s,u,w[u])\) 被割，表示不选 \(u\)
- 边 \((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，求其最小路径覆盖。
这里体现的重要思想有两个：
- 将一个点的不同状态拆分，化为左右部，分别求解
- 部分计算，合并答案
- 正难则反，拆分——>合并
首先，我们将在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题的变形题。