HDU-6532 Chessboard 2019广东省省赛B题（费用流）

骑猪看日落 2022-01-11 07:33 108阅读 0赞

## 题意：给出一张棋盘，其上一些位置上有一些棋子。现在又给出一些限制条件，如某行以下最多可以选取多少的棋子，某列以右最多可以选取多少棋子。每个棋子的位置按照一定的顺序给出，其顺序中的排名即是其价值，问可以达到的最大价值是多少。 ##

## 题解：费用流。离散化坐标，每行用一个点表示，每列也用一个点表示。表示第i-1行的点向表示第i行的点连边，容量为第i行及以后能拿的棋子数的上限，费用为0，同理表示相邻列的点两两连边。若第i行第j列上有棋子，则表示第i行的点向表示第j列的点连边，容量为1，费用为该棋子的价值。可以定义源点表示第0行，汇点表示第0列，源点到汇点的最大费用流即为答案。 ##

## 就是按照题解的建图方法，还有一些小细节：先要排序排除无用限制来减少限制边数，不然会超时。我用的办法是，按限制从小到大排序，大限制当且仅当它的行数小于小限制行数时才有用。列同理。这里想不明白的建议画图细细想。然后就是连边来表示限制条件：行的话就是(i-1)->i行连边，列的话就是i->(i-1)列连边，这是因为0行是源点0列是汇点所致的，行点要靠它的入边来限制流量，列点要靠出边来限制流量。建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：棋盘问题是一个很经典的网络流问题，把行列分成两部，通过这题学到了网络流建图的新姿势，很奇妙，但是感觉还是没搞透，还需二次领悟。 ##

## 代码：待补。参考[https://www.cnblogs.com/clno1/p/10957772.html][https_www.cnblogs.com_clno1_p_10957772.html]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220111/3af9f2faf294430b97cd0ce405ffab4d.png
[https_www.cnblogs.com_clno1_p_10957772.html]: https://www.cnblogs.com/clno1/p/10957772.html