Ford-Fulkerson

keyword

最大流　Ford-Fulkerson　C++

入力

流量を表す行列、sourceの番号、sinkの番号(いずれも0-base)を与える。行列については流れないとき0(実は負でも良いけど)を入れること。流量が実数の場合はアルゴリズムが終了する保証はない。

出力

sourceからsinkへの最大の流量を返す。必要に応じてflow matrixを返すこともできる。

計算量

時間計算量 O(m*maxflow) (maxflowはmatrixの最大の要素)。ただし整数の場合のみ。
空間計算量 O(n*n)。疎でも密でも変わらず。

注釈

残余グラフは実は作らなくても他ので代用が効く。メモリが厳しいときはここを削る。
動作は未検証。

template<typename T>
T FordFulkersonByMatrix(vector< vector<T> > &matrix, int source, int sink){
    int n = matrix.size();
    T maxCost = (T)0;
    vector< vector<T> > flowMat(n, vector<T>(n,0)), resMat = matrix;
    for(int i=0; i<n; i++)for(int j=0; j<n; j++)
        maxCost = max(maxCost,matrix[i][j]);

    while(1){
        stack<int> st;
        vector<int> parent(n,-1);
        st.push(source);
        while(!st.empty() && parent[sink] == -1){
            int tp = st.top(); st.pop();
            for(int i=0; i<n; i++){
                if(parent[i] == -1 && resMat[tp][i] > 0){
                    st.push(i);
                    parent[i] = tp;
                }
            }
        }
        if(parent[sink] == -1) break;
        T minCost = maxCost;
        for(int i=sink; i!=source; i = parent[i]){
            minCost = min(minCost, resMat[parent[i]][i]);
        }
        for(int i=sink; i!=source ; i = parent[i]){
            flowMat[parent[i]][i] += minCost;
            flowMat[i][parent[i]] -= minCost;
            resMat[parent[i]][i] -= minCost;
            resMat[i][parent[i]] += minCost;
        }
    }

    return accumulate(flowMat[source].begin(), flowMat[source].end(), (T)0);
}