{"id":121,"date":"2010-08-18T08:32:44","date_gmt":"2010-08-18T00:32:44","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=121"},"modified":"2012-03-03T08:32:59","modified_gmt":"2012-03-03T00:32:59","slug":"sgu-176-flow-construction","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/sgu-176-flow-construction\/","title":{"rendered":"SGU 176. Flow construction"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u6709\u4e0a\u4e0b\u754c\u7f51\u7edc\u7684\u6700\u5c0f\u6d41\u3002<br \/>\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/1363\">\u56e0\u4e3a\u662f\u4e00\u4e2a\u5b50\u6b65\u9aa4\uff0c\u5927\u5bb6\u90fd\u63a8\u8350\u5148\u505a\u8fd9\u4e2a\u9898\uff0c\u54b3\u54b3\u3002\u3002\u3002<\/a><br \/>\n&#8230; \u53d1\u73b0\u6c42\u6700\u5c0f\u6d41\u53ea\u662f\u9700\u8981\u628a\u6e90\u70b9\u548c\u6c47\u70b9\u4ea4\u6362\u53cd\u8fc7\u6765\u63a8\u56de\u53bb\u5c31\u884c\u4e86\uff0c\u4f46\u662f\u53ef\u80fd\u4f1a\u4ea7\u751f\u4e00\u4e2aBUG\u3002\u3002\u4f1a\u51fa\u73b0\u8d1f\u7684\u6700\u5c0f\u6d41\u3002#\uff08\u5206\u6790\u5176\u4ea7\u751f\u7684\u539f\u56e0\u662f\u6e90\u70b9\u548c\u6c47\u70b9\u4f1a\u7834\u574f\u4e86\u6d41\u5b88\u6052\uff0c\u5f53\u7136\u6e90\u70b9\u7834\u574f\u4e86\u6ca1\u5173\u7cfb\uff0c\u53ef\u662f\u6211\u4eec\u4e0d\u662f\u4ea4\u6362\u8fc7\u6765\u4e86\u561b\u3002#\uff09<\/p>\n<p>\u65b0\u5efa\u6e90\u70b9 0\uff0c\u5728 0 \u548c 1 \u4e4b\u95f4\u8fde\u4e00\u6761\u6d41\u91cf\u4e3a -\uff08steady_flow &#8211; max_flow\uff09\u7684\u8fb9\uff0c\u7136\u540e\u518d\u505a\u4e00\u6b21 Dinitz \u628a\u8d1f\u6d41\u63a8\u6210\u4e860.\u3002\u3002<br \/>\n\uff08\u8fd9\u4e2a\u9898\u3002\u3002\u3002\u53e6\u4e00\u4e2a\u4e0d\u8981\u60f3.#\u7684\u65b9\u6cd5\u662f\u4e8c\u5206 C[n][1] \u7684\u6d41\u91cf &#8230;\uff09<\/p>\n<pre lang=\"cpp\" file=\"Dinitz_more.cpp\">\r\n\/*\r\n    Author: xiaodao\r\n    Prob: SGU 176. Flow construction\r\n    Date: GMT +8 Aug.19th 04:41\r\n    Status: Accepted\r\n    Tags: Network-Flow, Dinitz\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\nusing namespace std;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 102, M = N*N\/2;\r\nint C[N][N], D[N];\r\nint x[M], y[M], l[M], r;\r\nint necessary_flow, steady_flow, max_flow;\r\nint n, m, s, t, ans;\r\n\r\n\r\n\r\n\r\nvoid bfs(){\r\n    int Q[N], head, tail;\r\n    memset(D, -1, sizeof(D));\r\n    head = 0; tail = 1; Q[0] = s; D[s] = 0;\r\n\r\n    int u, v;\r\n    while (head<tail){\r\n        u = Q[head];\r\n        for (v=1;v<=n;v++){\r\n            if (D[v]==-1 &#038;&#038; C[u][v]!=0){\r\n                Q[tail] = v; D[v] = D[u] + 1;\r\n                if (v == t) return;\r\n                tail++;\r\n            }\r\n        }\r\n        head++;\r\n    }\r\n}\r\n\r\n\r\nvoid dinitz(){\r\n    max_flow = 0;\r\n\r\n    bfs();\r\n    while (D[t]!=-1){\r\n        int stack[n+1], cur[n+1], top = 0;\r\n        for (int i=0;i<=n;i++) cur[i] = 1;\r\n        stack[0] = s;\r\n\r\n        int u, v;\r\n        while (top!=-1){\r\n            u = stack[top];\r\n\r\n            if (u == t){\r\n                int delta = INF, handle;\r\n                for (int i=0;i<top;i++){\r\n                    u = stack[i]; v = stack[i+1];\r\n                    if (C[u][v] < delta){\r\n                        delta = C[u][v];\r\n                        handle = i;\r\n                    }\r\n                }\r\n                max_flow += delta;\r\n                for (int i=0;i<top;i++){\r\n                    u = stack[i]; v = stack[i+1];\r\n                    C[u][v] -= delta; C[v][u] += delta;\r\n                }\r\n                top = handle;\r\n                continue;\r\n            }\r\n\r\n            for (v=cur[u];v<=n;v++)\r\n                if (D[u] + 1 == D[v] &#038;&#038; C[u][v]!=0) break;\r\n\r\n\r\n            if (v>n) D[u] = -1, top--;\r\n            else {\r\n                cur[u] = v + 1;\r\n                stack[++top] = v;\r\n            }\r\n        }\r\n        bfs();\r\n    }\r\n}\r\n\r\nvoid recover(){\r\n    s = 0; t = n; C[s][1] = -ans; dinitz();\r\n    ans = 0;\r\n}\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    n++; necessary_flow = 0;\r\n    for (int i=0;i<m;i++){\r\n        scanf(\"%d%d%d%d\", &#038;x[i], &#038;y[i], &#038;r, &#038;l[i]);\r\n        if (l[i]==1) l[i] = r;\r\n        C[x[i]][y[i]] += r - l[i];\r\n        C[0][y[i]] += l[i];\r\n        C[x[i]][n] += l[i];\r\n        necessary_flow += l[i];\r\n    }\r\n    steady_flow = 0;\r\n    C[n-1][1] = INF;\r\n}\r\n\r\n\r\nint main(){\r\n    while (cin >> n >> m){\r\n        init(); s = 0; t = n; dinitz();\r\n        if (max_flow!=necessary_flow) printf(\"Impossible\\n\");\r\n        else {\r\n            steady_flow = C[1][--n];\r\n            s = n; t = 1; C[n][1] = C[1][n] = 0; dinitz();\r\n            ans = steady_flow - max_flow;\r\n            if (ans < 0) recover(); \/\/ T T\r\n            cout << ans << endl;\r\n            for (int i=0;i<m;i++)\r\n                printf(\"%d \", C[y[i]][x[i]]  + l[i]);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<pre lang=\"cpp\" file=\"Binary_answer.cpp\">\r\n\/*\r\n    Author: xiaodao    \r\n    Prob: SGU 176. Flow construction \r\n    Date: GMT +8 Aug.19th 04:19\r\n    Status: Accepted        \r\n    Tags: Network-Flow, Dinitz\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\nusing namespace std;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 102, M = N*N\/2;\r\nint C[N][N], F[N][N], D[N];\r\nint x[M], y[M], l[M], r;\r\nint necessary_flow, max_flow;\r\nint n, m, s, t; int limit;\r\n\r\n\r\n\r\n\r\nvoid bfs(){\r\n    int Q[N], head, tail;\r\n    memset(D, -1, sizeof(D));\r\n    head = 0; tail = 1; Q[0] = s; D[s] = 0;\r\n\r\n    int u, v;\r\n    while (head<tail){\r\n        u = Q[head];\r\n        for (v=1;v<=n;v++){\r\n            if (D[v]==-1 &#038;&#038; F[u][v] != C[u][v]){\r\n                Q[tail] = v; D[v] = D[u] + 1;\r\n                if (v == t) return;\r\n                tail++;\r\n            }\r\n        }\r\n        head++;\r\n    }\r\n}\r\n\r\n\r\nvoid dinitz(){\r\n    memset(F, 0, sizeof(F));\r\n    max_flow = 0;\r\n\r\n    bfs();\r\n    while (D[t]!=-1){\r\n        int stack[n+1], cur[n+1], top = 0;\r\n        for (int i=0;i<=n;i++) cur[i] = 1;\r\n        stack[0] = s;\r\n\r\n        int u, v;\r\n        while (top!=-1){\r\n            u = stack[top];\r\n            if (u == t){\r\n                int delta = INF, handle;\r\n                for (int i=0;i<top;i++){\r\n                    u = stack[i]; v = stack[i+1];\r\n                    if (C[u][v] - F[u][v] < delta){\r\n                        delta = C[u][v] - F[u][v];\r\n                        handle = i;\r\n                    }\r\n                }\r\n                max_flow += delta;\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                top = handle;\r\n                continue;\r\n            }\r\n\r\n            for (v=cur[u];v<=n;v++)\r\n                if (D[u] + 1 == D[v] &#038;&#038; F[u][v] != C[u][v]) break;\r\n\r\n\r\n            if (v>n) D[u] = -1, top--;\r\n            else {\r\n                cur[u] = v + 1;\r\n                stack[++top] = v;\r\n            }\r\n        }\r\n        bfs();\r\n    }\r\n}\r\n\r\n\r\nint binary_search(int l, int r){\r\n    int m;\r\n    while (l < r){\r\n        m = (l + r) \/ 2;\r\n        C[n-1][1] = m; dinitz();\r\n        if (max_flow==necessary_flow) r = m;\r\n        else l = m + 1;\r\n    }\r\n    if (l == m + 1) C[n-1][1] = l, dinitz(); \/\/ T T.\r\n    return l;\r\n}\r\n\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C)); limit = 0;\r\n    necessary_flow = 0; n++;\r\n    for (int i=0;i<m;i++){\r\n        scanf(\"%d%d%d%d\", &#038;x[i], &#038;y[i], &#038;r, &#038;l[i]);\r\n        if (l[i]==1) l[i] = r;\r\n        C[x[i]][y[i]] += r - l[i];\r\n        C[0][y[i]] += l[i];\r\n        C[x[i]][n] += l[i];\r\n\r\n        necessary_flow += l[i];\r\n        if (x[i]==1) limit  += r;\r\n    }\r\n\r\n    C[n-1][1] = INF;\r\n}\r\n\r\n\r\nint main(){\r\n    while (cin >> n >> m){\r\n        init(); s = 0; t = n; dinitz();\r\n        if (max_flow!=necessary_flow) printf(\"Impossible\\n\");\r\n        else {\r\n            cout << binary_search(0 , limit) << endl;\r\n            for (int i=0;i<m;i++)\r\n                printf(\"%d \", F[x[i]][y[i]]  + l[i]);\r\n            printf(\"\\n\");\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>External link :<br \/>\nhttp:\/\/acm.sgu.ru\/problem.php?contest=0&problem=176<br \/>\nhttp:\/\/hi.baidu.com\/hefeizhousiyuan\/blog\/item\/f4775339adc438fa3b87ce16.html<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u6709\u4e0a\u4e0b\u754c\u7f51\u7edc\u7684\u6700\u5c0f\u6d41\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_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","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-121","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1X","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/121","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=121"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/121\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}