BZOJ.2879.[NOI2012]美食节(费用流SPFA)，python自学行吗

哎呀妈呀，眼看这道题竟然是费用流SPFA，这可是中国优秀选手专业切磋的题目之一啊！难度不言而喻，但是我相信只要用心学习，自学也是可以行得通的！

首先我们得明白，费用流是图论中的一类算法，主要用于求解网络流问题。什么是网络流呢？简单来说，就是在一张带权有向图中，经过某些限制，使得起点到终点的最大流量最大，或者最小费用最小。这其中，“最大流量”和“最小费用”就是网络流的两个目标。

费用流算法大概分为两类：最短路和最大流算法。其中，最短路算法又有SPFA算法和Dijkstra算法等多种算法。而最大流算法，则有Ford-Fulkerson算法和最大流最小割定理等经典算法。至于SPFA算法，就是在Dijkstra算法的基础上进行的一种优化。

接下来，我们开始了解本题。[NOI2012]美食节，题面简单粗暴，但要求解的问题却非常具有代表性。在一个n个点m条边的有向图中，每个点都有一个点权，每条边也都有一个费用和容量。求从起点到终点的最大权值，使得其满足所有边的容量限制。

实际上，这道题就是求图中的最大权最大流，可以用费用流来求解。我们可以先将最大权值进行确定，二分一个权值v，那么问题就转化成了一个标准的最大流问题。具体来说，我们可以将每个点表示为源点和汇点之间的双向边，权值为原点权，容量为1。对于每条边(u,v,c,w)，我们可以将(u,v)和(v,u)各接一条双向边。其中，(u,v)的容量为c，费用为-w；(v,u)的容量为inf，费用为w。经过这样的建图，就可以使用费用流算法求解最大权最大流了。这个具体实现过程可以参考代码实现。

最后，提醒一点，由于本题边权可能为负数，而SPFA算法不能处理负权环，因此在实现时需要特别考虑。可以加一个判别是否存在负环的函数，在费用流代码的开头使用即可。