poj1273(Edmonds-Karp)

这道题可以算是例题了。

求解最大流，采用EK算法，用广搜查找增广路径，找到后更新网络流矩阵，循环执行直至找不到增广路径为止。这里要小心的是重复边的情况。

程序也是参照了网上的模版来写的，有一些技巧。如果完全让我自己来实现这个算法，会写的比较难看。还是too young

#include <iostream>

#include <queue>

using namespace std;

const int MAX_N = ;

const int INF = INT_MAX;

int n, m;int flow[MAX_N][MAX_N];

int cap[MAX_N][MAX_N];

int sum;

int pre[MAX_N];

int a[MAX_N];

void Edomds_Karp()

{

    while (){

        memset(a, , sizeof(a));

        a[s] = INF;

        queue<int> Q;

        Q.push(1);

        while (!Q.empty()){

            int u = Q.front();

            Q.pop();

            for (int v = ; v <= m; v++){

                if (!a[v] && flow[u][v] < cap[u][v]){

                    Q.push(v);

                    int tmp = cap[u][v] - flow[u][v];

                    a[v] = a[u] > tmp ? tmp : a[u];

                    pre[v] = u;

                }

            }

        }

        if (a[m] == ){

            break;

        }

        sum += a[m];

        for (int i = m; i != s; i = pre[i]){

            flow[pre[i]][i] += a[m];

            flow[i][pre[i]] -= a[m];

        }

    }

}

int main()

{

    while (cin >> n >> m){

        memset(flow, , sizeof(flow));

        memset(cap, , sizeof(cap));

        sum = ;

        for (int i = ; i <= n; i++){

            int s, e, c;

            cin >> s >> e >> c;

            cap[s][e] += c;

        }

        Edomds_Karp();

        cout << sum << endl;

    }

    return ;

}