UVa11167 Monkeys in the Emei Mountain（网络流区间模型+输出方案）

亦凉 2022-10-02 10:59 12阅读 0赞

## 题意：有n只猴子，每只猴子都有一组参数(v,a,b)，表示这只猴子在时间段\[a,b\]之间必须要喝v个单位水，并且每个时间单位只能和一个单位水，每次至少喝一个单位。但是只有一个水池，并且这个水池最多只允许m只猴子同时喝水。问能否满足所有的猴子喝水，若能，输出任意一种可行的方案。 ##

## 分析：将每个猴子和每个喝水区间视作节点。将每只猴子向它对应的区间连弧，容量为该区间上能喝水的总单位数；从源点向每只猴子建弧，容量为对应猴子的总需求量；从每个区间向汇点建弧，容量为该区间单位长度乘以m，表示在该区间最多允许有m只猴子同时喝水。求得最大流看是否能满足最大需求，如果能，则输出方案，其中，猴子节点连向区间节点的弧上的容量便是一种可行方案，最后要注意区间合并。由于时间轴有至多50000长，如果按照上述的建边必定超时。而且我们可以注意到 n 至多100，那么可以划分出来的区间至多199个，我们可以通过离散化缩小数据规模。对于每只猴子我们怎么知道它在哪几个区间喝了水？对着从这只猴子出发的反向边检查一下就好，如果有流量说明属于这条边的正向边被流过（也就是说猴子去该边所指向的区间喝水了），且喝的水的容量就是反向边的流量。还有个要考虑的就是如果一个区间被好多猴子一起享用，那么直接对这个区间不断的循环取就好了。建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：网络流区间模型+输出方案，区间也可以转为点，区间数量少，数字大就离散化。 ##

## 代码：待补。可以参考[https://www.cnblogs.com/20143605--pcx/p/5072363.html][https_www.cnblogs.com_20143605--pcx_p_5072363.html]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220112/d13fa0419624494d833d9fb2612aaa7d.png
[https_www.cnblogs.com_20143605--pcx_p_5072363.html]: https://www.cnblogs.com/20143605--pcx/p/5072363.html