2010-1114

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目意思就是要在方格纸中建围墙，使X和E无法联通，然后每当有一个A不与任何的E联通时，收入就会增加这个A对应的权值，建围墙的花费是所经过的边权之和。
做法：
典型的网络流，题目实际上是要求一个割，枚举要围住哪些A，然后将这些A与X和源点连一条流量为无穷的边，把每个E和汇点连一条流量为无穷大的边，那么这个图的最小割就是在当前决定好要保护那些A的情况下建围墙的最小花费了。

题目意思就是要在方格纸中建围墙，使X和E无法联通，然后每当有一个A不与任何的E联通时，收入就会增加这个A对应的权值，建围墙的花费是所经过的边权之和。

做法：

典型的网络流，题目实际上是要求一个割，枚举要围住哪些A，然后将这些A与X和源点连一条流量为无穷的边，把每个E和汇点连一条流量为无穷大的边，那么这个图的最小割就是在当前决定好要保护那些A的情况下建围墙的最小花费了。