sgu-194-Reactor Cooling(无源汇有上下界最大流)

忘是亡心i 2022-01-11 16:09 283阅读 0赞

## 题意:给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。并且满足每根pipe一定的流量限制，范围为\[Li,Ri\].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。 ##

## 分析:这个模型比较特别，没源又没汇，而且每条弧除了有容量c之外，还多了一个下界b。 那就分析一下该模型的特点，既然无源无汇，那么每个结点就都要满足”入流=出流”这个流量平衡条件依此性质，就求出每个点的入流和出流，用d\[\]代表每个结点的入流-出流。接着设置一个超级源点S和一个超级汇点T，因为要满足所有结点的入流=出流，所以: 1.d\[u\] > 0的点，建立 (S->u)的边，容量为d\[u\]，2.d\[u\] < 0的点，建立(u->T)的边，容量为-d\[u\]，3.所给的边（u,v,c,b),建立(u->v)的边，容量为c - b，为什么是c - b，因为我们假设该边已经流了b的流量了。如果求出来的是满流，表示能满足每条边的下界，解释一下为什么，根据流量守恒的性质，所有点的入流=所有点的出流，所以满流的时候，就满足了。 为什么要这样建模，首先，d\[u\]>0的连向了源点，也就是说，从u出发的都是出流了，只要该边满流了，就能让u点的入流=出流了，d\[u\] < 0的情况相同。建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：无源无汇，抓住每个结点就都要满足”入流=出流”这个流量平衡的性质。 ##

## 代码：待补。参考[https://blog.csdn.net/L123012013048/article/details/49765891][https_blog.csdn.net_L123012013048_article_details_49765891]、[https://blog.csdn.net/qq\_33362864/article/details/78197823][https_blog.csdn.net_qq_33362864_article_details_78197823]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220110/6a44b0090cb04a7cb489e4159dd2465f.png
[https_blog.csdn.net_L123012013048_article_details_49765891]: https://blog.csdn.net/L123012013048/article/details/49765891
[https_blog.csdn.net_qq_33362864_article_details_78197823]: https://blog.csdn.net/qq_33362864/article/details/78197823