UVa 1659 Help Little Laura 最大费用循环流

桃扇骨 2022-10-02 13:45 43阅读 0赞

## 题意：  ##

## 平面上有m条有向线段连接了n个点。你从某个点出发顺着有向线段行走，给走过的每条线段涂一种不同的颜色，最后回到起点。你可以多次行走，给多个回路涂色（要么不涂色，要么就至少给一个回路上的边全部涂色）。可以重复经过一个点，但不能重复经过一条有向线段。如下图所示的是一种涂色方法（虚线表示未涂色）。每涂一个单位长度将得到X分，但每使用一种颜色将扣掉Y分。假设你拥有无限多种的颜色，问如何涂色才能使得分最大？输入保证若存在有向线段u -> v，则不会出现有向线段v -> u。n <= 100，m <= 500，1 <= X，Y <= 1000。对于坐标（x，y）0 <= x，y <= 1000。 ##

![\\epsfbox\{p4030.eps\}][epsfbox_p4030.eps]

## 分析： 本来要找环使得分最大（即最大费用循环流），为了用最小费用流建模，就边权取反，然后找负环增广（转换成最小费用循环流）。这个问题的解决方法和最小费用最大流有些类似，只不过不是求一条s-t的最小费用增广路，而是找整个图的一个负费用增广圈。沿着负费用增广圈进行增广之后，每个节点的流量平衡不会被破坏，而整个循环流的总费用变小了。求解最小费用循环流的伪代码就是： ##

while(find_negative_cycle()) augment();

## 根据残留网络的概念不难得出：找负费用增广圈等价于在残留网络中找负权圈，这正是Bellman-Ford算法的拿手好戏。建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：最大费用循环流模板~。   代码：待补。参考[https://blog.csdn.net/xl2015190026/article/details/52138200][https_blog.csdn.net_xl2015190026_article_details_52138200]。 ##

[epsfbox_p4030.eps]: /images/20220112/779b6babfec647f69c5f1e5438827eb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220112/655e5d7d6c59441dbdc7759f879b2406.png
[https_blog.csdn.net_xl2015190026_article_details_52138200]: https://blog.csdn.net/xl2015190026/article/details/52138200