目录
网络流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题的变形题。