SGU 176 有源汇上下界的最小流

蔚落 2022-01-10 00:49 209阅读 0赞

## 题意：给出N个点，M条有向边，如果有向边的标号是1的话，就表示该边的上界下界都为容量，如果有向边的标号为0的哈，表示该边的下界为0，上界为容量，现在问，从1到N的最小流是多少，并输出每条边的流量。 ##

## 思路：首先，还是处理出所有的结点的入流-出流，然后连向超级源点S，超级汇点T，和无源无汇的那种情况相同，把源汇当成普通结点，先跑出最大流了，再添加边，再跑一次最大流，接着得到的(t1->s1)流就是所求的最小流了这里解释一下为什么，首先，我们在不添加(t1-s1)的情况下，先跑了一次(S到T的)最大流，表示的是不提供流量的情况下，让那些能平衡流量结点的尽量去平衡，这样就能减少流量了接着添加了(t1-s1)了，再跑一次(S到T的最大流)的话，相当于是提供了流量了，在提供了流量的情况下，如果能满流，即满足所有边的下界的话，就表示找到可行流了。为什么是最小的，因为第一次已经将那些能平衡的尽量平衡了，不能平衡的，就需要流了，所以，这是在实在不能平衡的情况下，才给流的，所以这是最小流。建图如下。 ##

## ![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]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220109/0d2a8d7e0c8a46d0be6f8e24310e837d.png
[https_blog.csdn.net_L123012013048_article_details_49765891]: https://blog.csdn.net/L123012013048/article/details/49765891