题解 P5192 【Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流】

# Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流解题报告 标签： 解题报告 --- [Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流](https://www.luogu.com.cn/problem/P5192)解题报告： [可能更好的阅读体验](https://zybuluo.com/xiaoziyao/note/1694812) ~~先吐槽一下，这虽然是板子题，但看懂怎么建模还要一小会儿~~ ~~还有，为什么要把三倍经验合并啊~~ ## 题意与分析 题意：一共有$n$天，每天最多拍$D_i$张~~照骗~~照片，有$C_i$个取材对象，每个取材对象$T_{i,j}$需要拍$[L_{i,j},R_{i,j}]$的照片，同时$m$个少女中每个少女的~~照骗~~数量不得少于$G_i$。 我们很容易从~~标题：【模板】有源汇上下界最大流~~$“[L_{i,j},R_{i,j}]$”和“不得少于$G_i$”看出来需要求有源汇上下界最大流 ## 无源汇上下界可行流 我们考虑一个问题：在一张图中，每条边有流量下界和流量上界，求是否存在一种方案在满足流量平衡的情况下，使所有边满足上下界限制。 注意：这里的流量平衡指：对于所有点$x$，满足$\forall_{e\in E,e.to==x}e.flow=\forall_{e'\in E,e'.from==x}e'.flow$（$e.from$与$e.to$分别为一条边的两个点，$e.flow$为这条边实际的流量），即对于每个点都满足流入它的流量等于流出它的流量。 很容易想到一种想法，我们把上限减去下限，然后跑最大流。但是这个很显然是不满足的，因为经过操作后可能会形成这样的图：，这张图是很显然没有可行流的。但是经过操作后，原图会变为：，此时存在可行流。 我们发现答案前后不一的原因是经过这种操作后新图不满足流量平衡了，这就很麻烦了，跑不了最大流，~~而且也不能随便发明一个不需要流量平衡的最大流算法~~，因此我们想想如何经过玄学操作是新图满足流量平衡。 对了！原点和汇点还在旁边晾着，我们要让它们干活。因为最大流算法中源点和汇点可以不满足流量平衡，因此我们可以把锅推到源点和汇点上，同样是把每条边上限减去下限，但是对于每个点，我们计算$in_x=\forall_{e\in E,e.to==x}e.flow$，$out_x=\forall_{e\in E,e.from==x}e.flow$，为了满足流量平衡，$x$可以获得的流量肯定是$min(in_x,out_x)$，此时不满足流量平衡的地方就是$\left|in_x-out_x\right|$了。因此，对于所有的$in_x>out_x$，我们从$s$向$x$连一条上限为$in_x-out_x$的边来补齐由于流量平衡损失的流量；对于所有的$in_x==out_x$，可以连边可以不连边；对于所有的$in_x<out_x$，我们从$x$向$t$连一条上限为$out_x-in_x$的边补齐由于流量平衡损失的流量。 简单来说，所有连向$x$的边抬高了$x$一共$in_x$的下限，所有从$x$连出的边抬高了$x$一共$out_x$的下限。为了让$x$连入和连出处于同一个水平，我们需要用可以不满足流量平衡的$s$和$t$抬高或降低$x$的下限（等于从连入经过一次抬高/降低再连出），这样可以让$x$处于流量平衡的状态。 因此，这个步骤已经很明了了： 1. 统计每个点$x$的$in_x$与$out_x$，即连向$x$的边的流量之和与连出$x$的边的流量之和。 2. 对于每一条原图里的边，流量设为上限减去下限，因此得到一张新图。 3. 虚拟源点与汇点$s$和$t$，对于所有的$x$，如果$in_x>out_x$，则从$s$向$x$连一条$in_x-out_x$的边，否则从$x$向$t$连一条$out_x-in_x$的边。 4. 跑一遍从$s$到$t$的最大流，如果$s$连出的边可以满流（由于流量平衡，等价于连向$t$的边可以满流），证明存在可行流。 ## 有源汇上下界可行流 考虑有源点和汇点的上下界可行流，即在无源汇上下界可行流的基础上增加两个点不满足流量守恒。 由于流量平衡流出$s$的流量很显然与流入$t$的流量是相等的，那么我们很容易发现只要连接一条$(t,s,inf)$的边，原图就可以转化为无源汇上下界可行流的裸题了！ 因此，步骤为： 1. 从原图中的汇点向源点连一条上限为$inf$的边。 2. 跑一遍无源汇上下界可行流。 ## 有源汇上下界最大流 接下来，我们看有源汇的上下界最大流。我们并不满足于求可行流，在找可行流的基础上，还想找最大流，这样应该怎么办呢？ 我们先找到一个可行流$flow1$，此时我们“榨干”了连接虚拟源点和虚拟汇点的边，因此我们不能再跑一遍从虚拟源点到虚拟汇点的最大流，因为这根本没有意义。 但是这个可行流不一定是最大流，因为可行流只会跑满与虚拟源点和虚拟汇点相连的边，因此$flow1$最多就是这些边的上限和，此时在原图中可能会有边是跑不满的。 因此我们考虑计算$flow2$为$flow1$还能向上浮动的流量（这里需要感性理解），那么如何求$flow2$呢？其实向上浮动某些流量可以等价于在原图中跑出增广路（很显然，因为每跑出一个增广路就会让答案$+1$），因此我们跑一遍从原图中的源点到原图中的汇点的最大流，并设其答案为$flow2$。 此时$ans=flow1+flow2$。 注意一点，在跑原图的最大流时需要删去从原图汇点到原图源点的边，如果这条边没有删去，则会导致死循环。 但是与虚拟源点和虚拟汇点相连的边可以不删去，因为在求第一次最大流的时候就已经将这些边“榨干”了（因为是满流），否则根本不存在可行流。 步骤： 1. 跑出一个有源汇上下界可行流，如果满流则设其答案为$flow1$，否则不存在答案。 2. 删去从原图汇点到原图源点的边。 3. 跑从原图源点到原图汇点的最大流，设答案为$flow2$，则总答案$ans=flow1+flow2$。 ## 回归题目 让我们回归题目，~~很容易~~可以看出来题目的建模方式：先虚拟一个源点$s$和一个汇点$t$，然后每天和每位少女分别建一个点，$P_i$与$Q_i$。首先连接所有的$Q_i$和$t$，下限为$G_i$，上限为$inf$。然后，连接$s$和所有的$P_i$，下限为$0$，上限为$D_i$。对于第$i$天，取材对象为$T_{i,j}$，取材数量为$[L_{i,j},R_{i,j}]$时，连接$D_i$和$T_{i,j}$，下限为$L$，上限为$T$。这样，就完成了原图的建模。 然后就按照有源汇上下界最大流的建模继续就ok了。 ## 代码 注意：少女的编号是从$0$开始的，而且有多组数据，记得清零数组与变量 ``` #include<stdio.h> #include<queue> #include<string.h> #define inf 2147483647 using namespace std; const int maxn=1000005,maxm=1000005; int i,j,k,m,n,s,t,s1,t1,s2,t2,e,flg,ans,sum,anss; int start[maxn],to[maxm],then[maxm],worth[maxm],rev[maxm],dep[maxn],vis[maxn],in[maxn],out[maxn],G[maxn]; queue<int>q; inline int min(int a,int b){ return a<b? a:b; } inline void add(int x,int y,int z,int r){ then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,rev[e]=r; } inline void addedge(int x,int y,int z){ add(x,y,z,e+2),add(y,x,0,e); } void bfs(){ while(!q.empty()) q.pop(); for(int i=1;i<maxn;i++) dep[i]=inf,vis[i]=0; dep[s]=0; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=0; for(int i=start[x];i;i=then[i]){ int y=to[i]; if(worth[i]&&dep[y]>dep[x]+1){ dep[y]=dep[x]+1; if(vis[y]==0){ vis[y]=1; q.push(y); } } } } } int dfs(int x,int flw){ if(x==t){ flg=1,ans+=flw; return flw; } int rest=flw; for(int i=start[x];i;i=then[i]){ int y=to[i]; if(worth[i]&&dep[y]==dep[x]+1){ int newflw=dfs(y,min(rest,worth[i])); if(newflw>0){ rest-=newflw; worth[i]-=newflw,worth[rev[i]]+=newflw; if(rest==0) break; } else dep[y]=0; } } return flw-rest; } int Dinic(){ ans=0; while(1){ bfs(); if(dep[t]==inf) break; flg=1; while(flg){ flg=0; dfs(s,inf); } } return ans; } int main(){ while(~scanf("%d%d",&n,&m)){ sum=e=0; memset(start,0,sizeof(start)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); s1=n+m+1,t1=n+m+2,s2=n+m+3,t2=n+m+4; s=s2,t=t2; for(i=1;i<=m;i++){ scanf("%d",&G[i]); in[t1]+=G[i],out[n+i]+=G[i]; addedge(n+i,t1,inf-G[i]); } for(i=1;i<=n;i++){ int C,D,T,L,R; scanf("%d%d",&C,&D); addedge(s1,i,D); for(j=1;j<=C;j++){ scanf("%d%d%d",&T,&L,&R); T++; in[n+T]+=L,out[i]+=L; addedge(i,n+T,R-L); } } for(i=1;i<=n+m+2;i++){ if(in[i]>out[i]) addedge(s,i,in[i]-out[i]),sum+=in[i]-out[i]; else addedge(i,t,out[i]-in[i]); } addedge(t1,s1,inf); if(Dinic()!=sum){ puts("-1\n"); continue; } anss=worth[e]; worth[e]=worth[rev[e]]=0; s=s1,t=t1; anss+=Dinic(); printf("%d\n\n",anss); } return 0; } ``` ## 扩展-有源汇上下界最小流 我们看到有源点和汇点的上下界最小流，即在可行流的基础上要求流量最小。 我们先跑一遍可行流，设可行流为$flow1$ 则最小流为可行流$-$还能向下浮动的流量$flow2$ 其实我们可以发现还能向下浮动的流量就是从原图汇点到原图源点的最大流（感性理解）。 因此步骤为： 1. 跑出一个有源汇上下界可行流，如果满流则设其答案为$flow1$，否则不存在答案。 2. 删去从原图汇点到原图源点的边。 3. 跑从原图汇点到原图源点的最大流，设答案为$flow2$，则总答案$ans=flow1-flow2$。