网络流之增广路

这个我是看了一个博客，还比较好理解

http://www.cnblogs.com/fzl194/p/8855101.html

我就理解了一下代码

然后试着写了一些一个模板题

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

Sample Output

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 500;
typedef long long ll;
struct node
{
    int from, to;
    ll cap, flow;//起点，终点，容量，流量
    node(int from = 0, int to = 0, ll cap = 0, ll flow = 0) :from(from), to(to), cap(cap), flow(flow) {}
};
vector<node>e;//这个用来记录每一个水流
vector<int>G[maxn];//记录i起点的所有水流在e数组的位置
int p[maxn];//p数组表示i点前面的那个结点
ll a[maxn];//这个表示每一个节点经过的水流

void add(int u, int v, ll w)
{
    e.push_back(node(u, v, w, 0));
    e.push_back(node(v, u, 0, 0));
    int m = e.size();
    G[u].push_back(m - 2);
    G[v].push_back(m - 1);
}

ll MaxFlow(int s, int t)
{
    ll flow = 0;
    while (1)
    {
        //每一次循环都是在找增广路径
        //这个每次循环之后，e.flow都会增加，其实就相当于e.cap的减小，所以每一次都把a清空，就相当于就是改变了flow和cap
        // 就是重新走一次
        memset(a, 0, sizeof(a));
        queue<int>que;
        que.push(s);
        a[s] = inf;

        while (!que.empty())
        {
            int x = que.front();
            que.pop();
            for (int i = 0; i < G[x].size(); i++)
            {
                node &now = e[G[x][i]];
                if (!a[now.to] && now.cap > now.flow)
                    //这个a的判断应该是为了不重复搜索一个点
                    //后面的now.cap>now.flow这个是判断是否可以让水流经，注意这个now.flow可以是负数
                {
                    p[now.to] = G[x][i];
                    a[now.to] = min(a[x], now.cap - now.flow);
                    que.push(now.to);
                    //a代表这个点可以流出去的最大的水量，
                    //now.cap-now.flow这个其实才是真正的这个管子的容量，这个开始有点难理解
                    //因为第一次now.cap-now.flow就是now.cap   但是后面每一次while循环找增广路径，这个管子就装了之前那么多的水，就不管之前的了
                    //就相当于这个管子减小了，就是now.cap-now.flow
                    //还有一个特别的地方就是 有可能now.flow会是负数
                }
            }
            if (a[t]) break;//如果已经到达终点就可以出去了
        }
        if (!a[t]) break; //如果最后都无法流到t，则说明没有增广路了，所以就退出
        for (int i = t; i != s; i = e[p[i]].from)
        {
            e[p[i]].flow += a[t];
            e[p[i] ^ 1].flow -= a[t];
        }
        flow += a[t];
    }
    return flow;
}

void init()
{
    for (int i = 0; i <= maxn; i++) G[i].clear();
    e.clear();
}
int main()
{
    int n, m;
    while(cin >> n >> m)
    {
        init();
        for (int i = 1; i <= n; i++)
        {
            int a, b;
            ll w;
            cin >> a >> b >> w;
            add(a, b, w);
        }
        ll ans = MaxFlow(1, m);
        cout << ans << endl;
    }
    
    return 0;
}

网络流 之 增广路

网络流之增广路