zoj3229 Shoot the Bullet(有源汇有上下界的最大流)

电玩女神 2022-01-09 23:45 458阅读 0赞

## 题意：一个屌丝给m个女神拍照，计划拍照n天，每一天屌丝给给定的C个女神拍照，每天拍照数不能超过D张，而且给每个女神i拍照有数量限制\[Li，Ri\]，对于每个女神n天的拍照总和不能少于Gi，如果有解求屌丝最多能拍多少张照，并求每天给对应女神拍多少张照；否则输出-1。 ##

## 分析：要求解这个最大流，首先得保证上下界可行流有解。新增一个超级源点ss,超级汇点tt。点\[1,n\]视作n天，\[n+1,n+m\]视作m个女生。由源点s向\[1,n\]分别建容量为Di的弧，由于下界是0，所以不用分离出来。由\[n+1,n+m\]向汇点t建容量为INF - Gi的边，表示其下界为Gi,上界为正无穷（或者说假设已经留了Gi的流了）。对于天数i中女生j的上下界Lij与Rij，从i向j+n建容量为Rij-Lij的弧。记录每个点（包括s和t）的入流-出流的值cap\[i\]，若cap\[i\]>0,由超级源点ss向其建容量为cap\[i\]；若cap\[i\]<0,由该点向超级汇点tt建容量为-cap\[i\]的边。增设一条从d到s没有下界容量，上界容量为无穷的边，那么原图就变成了一个无源汇的循环流图。跑出ss到tt的最大流f，若f==由ss出发的所有边的流量上限之和，则说明有可行流。在确保有可行流的基础上，该题要求的是最大流，做法是在残余网上跑出s到t的最大流，得到的最大流即为所求答案。本题还需输出代表每天每人拍摄照片数的流量，则该流量 = 该弧流量下界 + 第二次跑出的自由流。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结： ##

## 代码：待补。参考[https://www.cnblogs.com/arbitrary/p/3123935.html][https_www.cnblogs.com_arbitrary_p_3123935.html]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220109/3139a66e15034f82be1d3e1bac725c26.png
[https_www.cnblogs.com_arbitrary_p_3123935.html]: https://www.cnblogs.com/arbitrary/p/3123935.html