最大流 pku1273 Drainage Ditches

Drainage Ditches
Time Limit: 1000MS        Memory Limit: 10000K
Total Submissions: 17239        Accepted: 6224

Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output

50

Source
USACO 93

题意描述：求1到M的最大流

SAP，bfs求原点到汇点的最小增广路径


这里有各种最大流的算法

2. Edmonds - Karp 算法

Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的 Dinic 算法都属于此。SAP 类算法可统一描述如下：

Shortest Augmenting Path
1 x <-- 0
2 while 在残量网络 G_x 中存在增广路 s ~> t
3     do 找一条最短的增广路径 P
4        delta <-- min{r_ij:(i,j) 属于 P}
5        沿 P 增广 delta 大小的流量
6        更新残量网络 G_x
7 return x

在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索 (BFS)，E-K 算法就直接来源于此。每次用一遍 BFS 寻找从源点 s 到终点 t 的最短路作为增广路径，然后增广流量 f 并修改残量网络，直到不存在新的增广路径。

E-K 算法的时间复杂度为 O(VE²)，由于 BFS 要搜索全部小于最短距离的分支路径之后才能找到终点，因此可以想象频繁的 BFS 效率是比较低的。实践中此算法使用的机会较少。

对最大流的一些疑问：为什么E-K算法要寻找“最短”的增广路径呢？应该是只要存在Augment path就行，不一定要求最短？

#include <iostream>
#include <string.h>
#include <deque>
using namespace std;

#define MAX_INT 0x7fffffff
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int N, M, map[210][210], pre[210], node_min[210], path_min[210];
deque<int> Q;

/*为bfs初始化*/
void initialize(int s)
{
    int i;
    memset(pre, 0, sizeof(pre));
    for (i=0 ; i<=M ; i++)
        node_min[i] = path_min[i] = MAX_INT;
    node_min[s] = 0;
}

bool bfs(int s, int t)
{
    int i, crt;

    initialize(s);
    Q.push_back(s);
    while (!Q.empty())
    {
        crt = Q.front();
        Q.pop_front();
        for (i=1 ; i<=M ; i++)
        {
            if (0 != map[crt][i] && (node_min[crt] + map[crt][i] < node_min[i]))
            {
                node_min[i] = node_min[crt] + map[crt][i];
                /*记录最短路径*/
                pre[i] = crt;
                path_min[i] = MIN(path_min[crt], map[crt][i]);
                Q.push_back(i);
            }
        }
    }
    
    if (MAX_INT == node_min[M])
        return false;
    return true;
}

int max_flow(int s, int t)
{
    int crt, fath, min, ret = 0;

    while (bfs(s, t))
    {
        /*按最短路径调整残留网络*/
        min = path_min[M];
        crt = M;
        while (crt != s)
        {
            fath = pre[crt];
            map[fath][crt] -= min;

            /*这里为什么要反向增加流？？*/


            map[crt][fath] += min;
            crt = fath;
        }
        ret += min;
    }

    return ret;
}

int main(int argc, char *argv[])
{
    int i, si, ei, ci, max;

    while (cin >> N >> M)
    {
        memset(map, 0, sizeof(map));
        for (i=0 ; i<N ; i++)
        {
            cin >> si >> ei >> ci;
            map[si][ei] += ci;
        }

        max = max_flow(1, M);
        cout << max << endl;
    }
}