最大ストリームアルゴリズムのFord-FulkersonアルゴリズムとEdmonds–Karpアルゴリズム

誘引子
一番大きな流れのテンプレートを何回も見ましたが、基本概念なども何回も見ました.強者同士のボードも使ったことがありますが、ネットが流れません.書いてみたことがありますが、一番簡単なアルゴリズムでも成功したことがありません.そして強者大神のコードに少しずつ猫を見て虎を描きます.でも、これは何の役にも立たないです.実はまだできません.しばらくすると書けなくなりますので、その時のAさんは照らし合わせて変数を変えたのでしょう.持続的に萎靡して、間欠的に戸惑っているのは資料を見ない時、特に他人のコードを見ないで完全に自分でテンプレートの問題を書いたと思います.
テーマ
hihocoder 1369http://hihocoder.com/problemset/problem/1369 hdu 3549http://acm.hdu.edu.cn/showproblem.php?pid=3549 二つのデータ範囲が極めて小さいテンプレートの練習問題
最大ストリームの問題
多くの重複を考えたくないです.ネット上に既にある基礎概念です.私の理解を述べたいだけです.一方通行の水道管しか考えられません.問題はソースから送金ポイントまでの最大の水の量を求めています.流量ネットワークとは、各辺にどれぐらいの水が流れているかを示す図です.各辺の制限によって、その辺の容量制限を超えてはいけないことは明らかです.残りのネットワークはどのぐらいの水が流れますか?一番重要なのは逆方向の理解です.一方の辺(u,v)(u,v)に対して、その一方の流量fを増加させることを選択すると、uからvまでの新たな残差容量はこの動作の前に残差流量からf fを減算します.
c’(u,v)＝c(u,v)−f c’(u,v)＝c(u,v)−f
vからuまでの残差流量を同時に増加させ(最初にvからuまで端がないと容量が0)、fを増加させる.
この容量の増加はどうやって分かりますか?
vからuまで選んだら
f’f’の流量は、元々変化する前の図のu〜vに相当する.
fこの流量は少ないです.
f’f’
限り
f′≦f′≦f,私達はすべて原図の中で少流の方式を通じて等価な実現を構成することができます.
e(u,v)e(u,v)を一つ追加します.
fの流量を同時に
e(v,u)e(v,u)を一つ追加します.
fの容量、
まず後ろに落ちるのを避けてください.e(u,v)e(u,v)の流れが多すぎて、少し少なめに流すべきですが、どうやって判断するか分かりません.
リバースサイドがあります.多流になったと判断する必要がない場合は、自然に含んでいます.実行可能なストリームを探している時に、送り側e(v,u)e(v,u)の一つの流れを通して、多流の流量を流します.
Ford-Fulkersonアルゴリズム
次にFord-Fulkersonアルゴリズムについて説明します.問題の解決方法を探すときは、ネットワークを残します.最初の残存ネットワークは容量ネットワークです.Ford-Fulkersonアルゴリズムは現在の残存ネットワークにおいて、ソースポイントからシンクポイントまでの経路を探し続けています.この経路の各容量値は0より大きい必要があります.このようなパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスパスがあれば、flow=m i n｛c e i｝、ei＿p＿a t(s,t)は、経路上の各辺にflowの流量を与えることができます.私たちの実行可能な流れの総量を増加させます.したがって、このような経路を拡大路と呼ぶ.私たちは残留ネットワークに基づいて解を求めるので、逆側を増加させながら.私たちは直接に残存ネットワークの修正を与えます.経路上の各辺e(u,v)e(u,v)の残存流量がflow f l o wを減少させます.同時にe(v,u)e(v,u)の残存流量にflow f l o Fold-Fulkerssonアルゴリズムを加えて、残存ネットワークの中で拡大路を探して、残存ネットワークを更新します.見つけられない時は、私たちはもう最大の流れを手に入れました.時間の複雑さについては、辺の容量が無理ならば、FordFulker sonアルゴリズムはずっと実行しても終わりません.しかし、容量値が整数であれば、拡大路が見つかった時間は最大O(E)O(E)であり、毎回見つかった拡大路の流量値は少なくとも1であり、時間複雑度はO(E f)O(E f)であるべきであり、fは最後の最大ストリーム問題の解である.終了時間と最大流量値に関係なく動作時間を保証するFordFulker sonアルゴリズムの変数はEdmonds–Karpアルゴリズムである.以上はウィキペディアを参考にしました.理解の誤りがあれば指摘してください.
Edmonds–Karpアルゴリズム
上述したように、Edmonds–KarpアルゴリズムはFordFulker sonアルゴリズムの具体化、または変形といえる.Ford-Fulkersonアルゴリズムは具体的に述べていません.どのように増長路を探すかはdfs、bfsを採用できます.Edmonds–Karpアルゴリズムは大体Ford-Fulker sonアルゴリズムと同じですが、見つかったショートは現在の残存ネットワークの中で最小のパスです.つまり、一番短絡(辺の数が一番短い)を探します.最も短絡的な方法を探しているのはBFSです.その時間の複雑さは:
O(V E 2)O(V E 2)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m;
int pointCount,edgeCount;
const int kMaxPointCount = 500;
const int kMaxInt = 0x7fffffff;
typedef map<int,int> toVCapacity; //   map，  ：     ，            
toVCapacity edgeFrom[kMaxPointCount+2]; //    0  

// hihocoder 1369
// hdu 3549

// reverseWay                 ，     end
//        end-v1-v2-v3-v4-v5-...-start (      ，(v1,end)    )         end
bool getAWayByBfs(int pointCount,int edgeCount,int start,int end,toVCapacity remainCapacityFrom[],int pre[],vector<int>&reverseWay,int flows[])
{
    const int notVisited = -1;/*-1       ，       ,     memset，         */
    const int noPre = -2; /*                 */
    reverseWay.clear();
    memset(pre,notVisited,sizeof(int)*pointCount);
    queue<int>q;
    flows[start] = kMaxInt; pre[start] = noPre; q.push(start);
    int u,v,remainCapacity;
    toVCapacity::iterator edgeIt,tmpEndEdgeIt;
    bool reachEndFlag = false;
    while ((!reachEndFlag) && (!q.empty())) {
        u = q.front(); q.pop();
        edgeIt = remainCapacityFrom[u].begin();
        tmpEndEdgeIt = remainCapacityFrom[u].end();
        while (edgeIt != tmpEndEdgeIt) {
            v = edgeIt->first;
            remainCapacity = edgeIt->second;
            if (notVisited == pre[v] && remainCapacity > 0) {
                flows[v] = min(flows[u],remainCapacity);
                pre[v] = u; q.push(v);
                if (v == end) {
                    reachEndFlag = true;
                    break;
                }
            }
            ++edgeIt;
        }
    }
    if (pre[end] == notVisited)
        return false;

    v = end;
    while (v != start) {
        //cout<
        v = pre[v];
        reverseWay.push_back(v);
    }
    //cout<
    return true;
}

void addCapacity(toVCapacity remainCapacityFrom[],int u,int v,int addition)
{
    toVCapacity::iterator it;
    it = remainCapacityFrom[u].find(v);
    if (it == remainCapacityFrom[u].end()) {
        if (addition > 0) {
            remainCapacityFrom[u].insert(pair<int,int>(v,addition));
        } else if (addition < 0) {
            //cout<
            //exit(0);
        } // == 0, ignore
    } else {
        it->second += addition;
        if (it->second == 0) {
            remainCapacityFrom[u].erase(it);
        } else if (it->second < 0) {
            //cout<
            //exit(0);
        } // else ... ignore
    }
}

int getMaxFlow(int pointCount,int edgeCount,int start,int end,toVCapacity remainCapacityFrom[])
{
    int maxFlow = 0;
    int flows[pointCount+2],flow;
    int pre[pointCount+2];
    vector<int>reverseWay;
    vector<int>::iterator way_it;
    int u,v;
    while (1) {
        // find a path
        // if can,then we modify,or we break out
        if (!getAWayByBfs(pointCount,edgeCount,start,end,remainCapacityFrom,pre,reverseWay,flows))
            break;
        // reverseWay               ，     end
        flow = flows[end];
        v = end; way_it = reverseWay.begin();
        while (way_it != reverseWay.end()) {
            u = *way_it;
            addCapacity(remainCapacityFrom,u,v,-flow);
            addCapacity(remainCapacityFrom,v,u,flow);
            v = u; ++way_it;
        }
        maxFlow += flow;
    }
    return maxFlow;
}

int main1()
{
    char ln = '
';
    cin>>n>>m; //      
    pointCount = n; edgeCount = 2*m;
    int u,v,c;
    //            1  ，   1，   n
    for (int i = 0; i< pointCount; ++i)
        edgeFrom[i].clear();
    for (int i = 0;i < m; ++i) {
        cin>>u>>v>>c;
        --u,--v;
        //edgeFrom[u].insert(pair(v,c));
        //                 ，    
        // 1 2 3
        // 1 2 6
        //        1 2 3     1 2 6    insert    ，     
        //               ，        1 2 3               
        //     wa    
        //                   ，     ，              addCapacity    
        addCapacity(edgeFrom,u,v,c);
    }
    int ans = getMaxFlow(pointCount,edgeCount,0,pointCount-1,edgeFrom);
    cout<return 0;
}

int main()
{
    // for hdu
    /*int T;
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    for (int i = 1; i <= T; ++i) {
        cout<
    //for hihocoder
    main1();
    return 0;
}