{"id":126,"date":"2010-08-13T08:34:49","date_gmt":"2010-08-13T00:34:49","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=126"},"modified":"2012-03-03T19:35:56","modified_gmt":"2012-03-03T11:35:56","slug":"%e6%9c%80%e5%a4%a7%e6%b5%81%e3%80%82%e3%80%82%e3%80%82%e3%80%82","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e6%9c%80%e5%a4%a7%e6%b5%81%e3%80%82%e3%80%82%e3%80%82%e3%80%82\/","title":{"rendered":"\u6700\u5927\u6d41\u3002\u3002\u3002\u3002"},"content":{"rendered":"<h3>I. Fold-Forkson Method <\/h3>\n<p>As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path. <\/p>\n<p>1. First, We use a general dfs to find the augmenting path.<br \/>\n2. When we finding augmenting paths with breadth-first search. Things get changed. &#038;&#038; we got .. Edmonds_Karp Algorithm .<\/p>\n<pre lang=\"cpp\" file=\"Fold-Forkson.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nint stack[N], top; \/\/Stack..\r\nbool visited[N];\r\n\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nint n, m, ans;\r\n\r\ninline void push(int x){\r\n    \/\/cout << x << endl;\r\n    stack[++top] = x;\r\n    visited[x] = true;\r\n}\r\n\r\ninline void pop(){\r\n    visited[stack[top]] = false;\r\n    top--;\r\n}\r\n\r\ninline bool empty(){\r\n    return top==-1;\r\n}\r\n\r\n\r\n\r\nvoid stat(){\r\n    ans = 0;\r\n    for (int i=2;i<=n;i++)\r\n        ans += F[1][i];\r\n}\r\n\r\n\r\n\r\n\r\n\r\nbool find_path(){\r\n    int cur[N];\r\n    memset(visited, false, sizeof(visited));\r\n    for (int i=1;i<n;i++) cur[i] = 2;\r\n    top = -1; push(1);\r\n\r\n    int u, v;\r\n    while (!empty()){\r\n        u = stack[top];\r\n\r\n        for (v=cur[u];v<=n;v++)\r\n            if (!visited[v] &#038;&#038; F[u][v] < C[u][v]) break;\r\n\r\n        if (v > n) pop();\r\n        else{\r\n            push(v);\r\n            if (v == n) return true;\r\n            cur[u] = v + 1;\r\n        }\r\n    }\r\n\r\n    return false;\r\n}\r\n\r\nvoid add_path(){\r\n    int u, v; int delta = INF;\r\n\r\n    for (int i=0;i<top;i++){\r\n        u = stack[i]; v = stack[i+1];\r\n        delta = min(delta, C[u][v] - F[u][v]);\r\n    }\r\n\r\n    for (int i=0;i<top;i++){\r\n        u = stack[i]; v = stack[i+1];\r\n        F[u][v] += delta, F[v][u] -= delta;\r\n    }\r\n\r\n}\r\n\r\n\r\nvoid dfs_method(){\r\n    while (find_path())\r\n        add_path();\r\n    stat();\r\n}\r\n\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\n\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); dfs_method();\r\n    cout << ans << endl;\r\n}\r\n<\/pre>\n<pre lang=\"cpp\" file=\"Edmonds_Karp.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nstruct rec{\r\n    int v, p, k;\r\n    \/\/ Vertex, Parient ,key\r\n};\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nbool V[N]; rec Q[N]; \/\/ Visited, Queue..\r\nint head, tail;\r\nint n, m, ans;\r\n\r\nbool find_path(){\r\n    memset(V, false, sizeof(V));\r\n    Q[0].v = 1; Q[0].k = INF; V[1] = true;\r\n    head = 0; tail = 1;\r\n    int u, v;\r\n\r\n    while (head<tail){\r\n        u = Q[head].v;\r\n\r\n        for (v=2;v<=n;v++){\r\n            if (!V[v] &#038;&#038; F[u][v] < C[u][v]){\r\n                Q[tail].v = v; Q[tail].p = head;\r\n                Q[tail].k = min(Q[head].k, C[u][v] - F[u][v]);\r\n                if (v == n) return true;\r\n                V[v] = true; tail++;\r\n            }\r\n        }\r\n        head++;\r\n\r\n    }\r\n    return false;\r\n}\r\n\r\nvoid add_path(){\r\n    int u, v; int delta = Q[tail].k;\r\n\r\n    while (tail!=0){\r\n        u = Q[head].v; v = Q[tail].v;\r\n        F[u][v] += delta; F[v][u] -= delta;\r\n        tail = head; head = Q[head].p;\r\n    }\r\n}\r\n\r\nvoid stat(){\r\n    ans = 0;\r\n    for (int i=2;i<=n;i++)\r\n        ans += F[1][i];\r\n}\r\n\r\nvoid Edmonds_Karp(){\r\n    while (find_path())\r\n        add_path();\r\n    stat();\r\n}\r\n\r\n\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); Edmonds_Karp();\r\n    cout << ans << endl;\r\n}\r\n<\/pre>\n<p><\/bk><br \/>\n<\/bk><br \/>\n<\/bk><br \/>\n<\/bk><br \/>\n<\/bk><\/p>\n<h3>II. Dinitz Blocking Flow Method<\/h3>\n<p>In each phase the algorithms builds a layered graph with breadth-first search on the residual graph.<\/p>\n<pre lang=\"cpp\" file=\"Dinitz.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <list>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nstruct rec{\r\n    int v, p, k;\r\n    \/\/ Vertex, Key ...\r\n    \/\/ Point to key ...\r\n};\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nint L[N]; \/\/ Leval ...\r\nint n, m, ans;\r\n\r\n\r\n\r\nvoid stat(){\r\n    ans = 0;\r\n    for (int i=2;i<=n;i++)\r\n        ans += F[1][i];\r\n}\r\n\r\nvoid bfs(){\r\n    memset(L, -1, sizeof(L));\r\n\r\n    int Q[N], head, tail;\r\n\r\n    head = 0; tail = 1; Q[0]  = 1;\r\n    L[1] = 0;\r\n\r\n    int u, v;\r\n    while (head<tail){\r\n        u = Q[head];\r\n        for (v=2;v<=n;v++){\r\n            if (L[v]==-1 &#038;&#038; F[u][v] < C[u][v]){\r\n                Q[tail] = v; L[v] = L[u] + 1;\r\n                if (v == n) return;\r\n                tail++;\r\n            }\r\n        }\r\n        head++;\r\n    }\r\n}\r\n\r\n\r\n\r\nvoid dinic(){\r\n    bfs();\r\n    while (L[n]!=-1){\r\n        rec stack[N]; int cache[N-1], top = 0;\r\n        for (int i=1;i<n;i++)\r\n            cache[i] = 2;\r\n        stack[0].v = 1; stack[0].k = INF;\r\n\r\n        int u, v;\r\n        while (top!=-1){\r\n            u = stack[top].v;\r\n\r\n            if (u == n){\r\n                int delta = stack[top].k;\r\n                for (int i=0;i<top;i++){\r\n                    u = stack[i].v; v = stack[i+1].v;\r\n                    F[u][v] += delta;\r\n                    F[v][u] -= delta;\r\n                }\r\n\r\n                top = stack[top].p;  \/\/#\r\n\r\n                for (int i=1;i<=top;i++)\r\n                    stack[i].k -= delta;\r\n                continue;\r\n            }\r\n\r\n\r\n\r\n            for (v=cache[u];v<=n;v++){\r\n                if (C[u][v] == F[u][v]) continue; \/\/#\r\n                if (L[u] + 1 == L[v]) break;\r\n                \/\/if (L[u] < L[v]) break;\r\n            }\r\n\r\n            if (v>n){\r\n                L[u] = -1;\r\n                top--;\r\n            }\r\n            else{\r\n                cache[u] = v+1; top++;\r\n                stack[top].v = v;\r\n                if (C[u][v] - F[u][v] < stack[top-1].k){\r\n                    stack[top].k = C[u][v] - F[u][v];\r\n                    stack[top].p = top-1;\r\n                }\r\n                else{\r\n                    stack[top].k = stack[top-1].k;\r\n                    stack[top].p = stack[top-1].p;\r\n                }\r\n            }\r\n        }\r\n        bfs();\r\n    }\r\n    stat();\r\n}\r\n\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\n\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); dinic();\r\n    cout << ans << endl;\r\n}\r\n<\/pre>\n<p><\/bk><br \/>\n<\/bk><br \/>\n<\/bk><br \/>\n<\/bk><br \/>\n<\/bk> <\/p>\n<h3>III. Push-Relabel Method.  <\/h3>\n<p>Since 1976. A New Approach to the Maximum-Flow Problem ...<br \/>\n1. General push-relabel maximum flow algorithm.<br \/>\n2. Push-relabel algorithm with FIFO vertex selection rule...<br \/>\n(Although.. A still have some question between it and the Relabel_to_Frontalgorithm... )<\/p>\n<pre lang=\"cpp\" file=\"Push-Relabel.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nint H[N], E[N]; \/\/ .Height, Excess ...\r\nint n, m, ans;\r\n\/\/bool sign;\r\n\r\n\r\n\r\n\r\nvoid push(int u, int v, int delta){\r\n    F[u][v] += delta; F[v][u] -= delta;\r\n    E[u] -= delta; E[v] += delta;\r\n}\r\n\r\nvoid relabel(int u){\r\n    H[u]++;\r\n}\r\n\r\nvoid discharge(int u){\r\n    for (int v=1;v<=n;v++){\r\n        if (H[u] == H[v] + 1 &#038;&#038; F[u][v] < C[u][v]){\r\n            push(u, v, min(E[u], C[u][v] - F[u][v]));\r\n            if (E[u]==0) return;\r\n        }\r\n    }\r\n    relabel(u);\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nvoid push_relabel(){\r\n    memset(E, 0, sizeof(E));\r\n    memset(H, 0, sizeof(H));\r\n    E[1] = INF; H[1] = n;\r\n\r\n    for (int i=2;i<=n;i++){\r\n        if (C[1][i] > 0) {\r\n            push(1, i, C[1][i]);\r\n            if (i!=n) H[i] = 1;\r\n        }\r\n    }\r\n\r\n\r\n    do{\r\n        \/\/As long as there is legal push or relabel operation\r\n        for (int u=2;u<n;u++){\r\n            if (E[u] == 0) continue;\r\n            discharge(u);\r\n        }\r\n    } while (E[1] + E[n] != INF); \/\/(sign);\r\n}\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); push_relabel();\r\n    cout << E[n] << endl;\r\n}\r\n<\/pre>\n<pre lang=\"cpp\" file=\"Push-Relabel.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nint H[N], E[N]; \/\/ .Height, Excess ...\r\nint Q[N]; int head, tail; \/\/ Queue...\r\nint n, m, ans;\r\n\r\n\r\n\r\nvoid push(int u, int v, int delta){\r\n    F[u][v] += delta; F[v][u] -= delta;\r\n    E[u] -= delta; E[v] += delta;\r\n}\r\n\r\nvoid relabel(int u){\r\n    \/*\r\n    H[u] = INF;\r\n    for (int v=1;v<=n;v++){\r\n        if (F[u][v] < C[u][v])\r\n            H[u] = min(H[u], H[v]+1);\r\n    }\r\n    *\/\r\n    H[u]++;\r\n}\r\n\r\nvoid discharge(int u){\r\n    for (int v=1;v<=n;v++){\r\n        if (H[u] == H[v] + 1 &#038;&#038; F[u][v] < C[u][v]){\r\n            if (v!=n &#038;&#038; E[v] == 0) {\r\n                Q[tail] = v;\r\n                tail = (tail + 1) % N;\r\n            }\r\n            push(u, v, min(E[u], C[u][v] - F[u][v]));\r\n            if (E[u] == 0) return;\r\n        }\r\n    }\r\n\r\n    Q[tail] = u;\r\n    tail = (tail + 1) % N;\r\n    relabel(u);\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\r\nvoid push_relabel(){\r\n    memset(E, 0, sizeof(E));\r\n    memset(H, 0, sizeof(H));\r\n    E[1] = INF; H[1] = n;\r\n    head = 0; tail = 0;\r\n    for (int i=2;i<=n;i++){\r\n        if (C[1][i] > 0) {\r\n            push(1, i, C[1][i]);\r\n            if (i!=n) H[i] = 1, Q[tail++] = i;\r\n        }\r\n    }\r\n\r\n    while (head!=tail){\r\n        discharge(Q[head]);\r\n        head = (head + 1) % N;\r\n    }\r\n}\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); push_relabel();\r\n    cout << E[n] << endl;\r\n}\r\n\r\n<\/pre>\n<pre lang=\"cpp\" file=\"Relabel_to_Front.cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: ditch\r\n    LANG: CPP\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <list>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 1001;\r\nint C[N][N], F[N][N]; \/\/ Capacity, Flow..\r\nint H[N], E[N]; \/\/ .Height, Excess ...\r\nint n, m, ans;\r\nbool changed;\r\n\r\n\r\n\r\nvoid push(int u, int v, int delta){\r\n    F[u][v] += delta; F[v][u] -= delta;\r\n    E[u] -= delta; E[v] += delta;\r\n}\r\n\r\nvoid relabel(int u){\r\n\r\n    \/*\r\n    H[u] = INF;\r\n    for (int v=1;v<=n;v++){\r\n        if (F[u][v] < C[u][v])\r\n            H[u] = min(H[u], H[v]+1);\r\n    }*\/\r\n    H[u]++;\r\n}\r\n\r\nvoid discharge(int u){\r\n    if (E[u]==0){\r\n        changed = false;\r\n        return;\r\n    }\r\n\r\n    changed = true;\r\n    for (int v=1;v<=n;v++){\r\n        if (u == v) continue;\r\n        if (H[u] > H[v] && F[u][v] < C[u][v]){\r\n            push(u, v, min(E[u], C[u][v] - F[u][v]));\r\n            if (E[u]==0) {changed = false; return;}\r\n        }\r\n    }\r\n    relabel(u);\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\r\nvoid relabel_to_front(){\r\n    \/\/Relabel-to-front algorithm, ie. using FIFO heuristic\r\n\r\n    \/\/1.Send as much flow from s as possible.\r\n    memset(E, 0, sizeof(E));\r\n    memset(H, 0, sizeof(H));\r\n    E[1] = INF; H[1] = n;\r\n    for (int i=2;i<=n;i++){\r\n        if (C[1][i] > 0) {\r\n            push(1, i, C[1][i]);\r\n            if (i!=n) H[i] = 1;\r\n        }\r\n    }\r\n\r\n    \/\/2.Build a list of all nodes except s and t.\r\n    list<int> L;\r\n    for (int i=2;i<n;i++)\r\n        L.push_back(i);\r\n\r\n\r\n    \/\/3.As long as we have not traversed the entire list:\r\n    list<int>::iterator it=L.begin();\r\n    while (it!=L.end()){\r\n        \/\/1.Discharge the current node.\r\n        discharge(*it);\r\n        \/\/2.If the height of the current node changed:\r\n        if (changed){\r\n            L.push_front(*it); L.erase(it);\r\n            it = L.begin();\r\n        }\r\n        else\r\n            it++;\r\n    }\r\n}\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    memset(F, 0, sizeof(F));\r\n    cin >> m >> n;\r\n    int x, y, c;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        C[x][y] += c;\r\n    }\r\n}\r\n\r\nint main(){\r\nfreopen(\"ditch.in\",\"r\",stdin);\r\nfreopen(\"ditch.out\",\"w\",stdout);\r\n    init(); relabel_to_front();\r\n    cout << E[n] << endl;\r\n}\r\n\r\n<\/pre>\n<h3>External link :<\/h3>\n<p>http:\/\/en.wikipedia.org\/wiki\/Push-relabel_maximum_flow_algorithm<br \/>\nhttp:\/\/www.nocow.cn\/index.php\/Translate:USACO\/ditch<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I. Fold-Forkson Method As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path. 1. First, We use a general dfs to find the augmenting path. 2. When we finding augmenting paths with breadth-first search. Things get changed. &#038;&#038; we got .. Edmonds_Karp Algorithm [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-126","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-22","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/126","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=126"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/126\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=126"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=126"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=126"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}