{"id":117,"date":"2010-08-21T08:30:14","date_gmt":"2010-08-21T00:30:14","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=117"},"modified":"2012-03-03T08:30:27","modified_gmt":"2012-03-03T00:30:27","slug":"sgu-212-data-transmission","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/sgu-212-data-transmission\/","title":{"rendered":"SGU 212. Data Transmission"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u7ed9\u5b9a\u4e00\u5f20\u5206\u5c42\u56fe\uff0c\u6c42\u4e00\u6b21\u963b\u585e\u6d41&#8230;<br \/>\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>&#8230; \u6211\u8fd8\u6709\u4e1c\u897f\u9700\u8981\u786e\u8ba4\u3002<\/p>\n<pre lang=\"cpp\" file=\"Dinitz_with_greedy_initflow.cpp\">\r\n\/*\r\n    Author: xiaodao\r\n    Prog: ZOJ 2364 \/ SGU 212. Data Transmission\r\n    Status: Labeled\r\n    Last modify: GMT +8 Aug 22th 01:52\r\n    Tags: Network_flow\r\n*\/\r\n\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <vector>\r\n\r\nusing namespace std;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 1500, M = 300000 * 2;\r\nstruct edge{\r\n    int v, c;\r\n    void insert(int, int);\r\n} E[M+1]; int edge_count;\r\nvector<int> adj[N+1], reverse_adj[N+1]; int D[N+1];\r\nint n, m, l, s, t;\r\n\r\n\r\nint _r(int x){\r\n    return x ^ 1;\r\n}\r\n\r\nvoid edge::insert(int a, int b){\r\n    v = a; c = b;\r\n}\r\n\r\nvoid add_edge(int x, int y, int c){\r\n    adj[x].push_back(edge_count); E[edge_count++].insert(y, c);\r\n}\r\n\r\nvoid add_reverse_edge(int x, int y, int c){\r\n    reverse_adj[x].push_back(edge_count); E[edge_count++].insert(y, c);\r\n}\r\n\r\n\r\n\r\n\r\n\r\nvoid Dinitz(){\r\n    \/\/bfs();\r\n    \/\/while (D[t]!=-1){\r\n        int stack[N+1], cur[N+1], top = 0;\r\n        memset(cur, 0, sizeof(cur));\r\n        stack[0] = M;\r\n\r\n        int u; size_t i;\r\n        while (top!=-1){\r\n            u = E[stack[top]].v;\r\n\r\n            \/\/cout << u << endl;\r\n\r\n            if (u == t){\r\n                int handle = 1;\r\n                for (int i=2;i<=top;i++)\r\n                    if (E[stack[i]].c < E[stack[handle]].c)\r\n                        handle = i;\r\n\r\n\r\n                int delta = E[stack[handle]].c;\r\n\r\n                for (int i=1;i<=top;i++){\r\n                    E[stack[i]].c -= delta;\r\n                    E[_r(stack[i])].c += delta;\r\n                }\r\n\r\n                for (int i=handle;i<=top;i++) \/\/###\r\n                    cur[E[stack[i]].v] = 0; \/\/ ###\r\n                top = handle - 1;\r\n                continue;\r\n            }\r\n\r\n            for (i=cur[u];i<adj[u].size();i++){\r\n                edge &#038;arc = E[adj[u][i]];\r\n                if (D[arc.v] == D[u] + 1 &#038;&#038;  arc.c != 0) break;\r\n            }\r\n            if (i == adj[u].size()){\r\n                D[u] = -1; \/\/~\r\n                top --;\r\n            }\r\n            else {\r\n                stack[++top] = adj[u][i];\r\n                cur[u] = i + 1;\r\n            }\r\n        }\r\n      \/\/  bfs();\r\n    \/\/}\r\n}\r\n\r\n\r\n\r\nvoid print(){\r\n    for (int i=1;i<edge_count;i+=2){\r\n        printf(\"%d\\n\", E[i].c);\r\n    }\r\n}\r\n\r\nvoid init(){\r\n    vector<int> layer[N+1];\r\n    long long excess[N+1];\r\n    cin >> n >> m >> l;\r\n\r\n    edge_count = 0;\r\n    for (int i=1;i<=n;i++)\r\n        adj[i].clear(), reverse_adj[i].clear();\r\n    for (int i=1;i<=l;i++)\r\n        layer[i].clear();\r\n\r\n\r\n    for (int i=1;i<=n;i++){\r\n        scanf(\"%d\", &#038;D[i]); layer[D[i]].push_back(i);\r\n        if (D[i] == 1) s = i;\r\n        else if (D[i] == l) t = i;\r\n    }\r\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        add_edge(x, y, c);\r\n        add_reverse_edge(y, x, 0);\r\n    }\r\n\r\n    E[M].v = s; \/\/ ~\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\/* \u6211\u662f\u8d2a\u5fc3\u521d\u59cb\u6d41\u3002\u3002\u3002 *\/\r\n\r\n\/* \u6b65\u9aa4\u4e00\uff1a\u704c\u6c34 *\/\r\n\r\n    memset(excess, 0, sizeof(excess));\r\n    \/\/excess[s] = INF;\r\n    excess[s] = ((long long)1 << 63 ) - 1;\r\n    for (int i=1;i<l;i++){\r\n        for (size_t j=0;j<layer[i].size();j++){\r\n            int u = layer[i][j];\r\n            for (size_t k=0;k<adj[u].size();k++){\r\n                edge &#038;arc = E[adj[u][k]], &#038;rev = E[_r(adj[u][k])];\r\n                \/* ????????? *\/\r\n                if (excess[u] < arc.c){\r\n                    rev.c += excess[u]; arc.c -= excess[u];\r\n                    excess[arc.v] += excess[u]; excess[u] = 0;\r\n                    break;\r\n                }\r\n                else {\r\n                    excess[u] -= arc.c; excess[arc.v] += arc.c;\r\n                    rev.c += arc.c; arc.c = 0;\r\n                }\r\n            }\r\n        }\r\n    }\r\n\r\n\/* \u6b65\u9aa4\u4e8c\uff1a\u9000\u6f6e \/ \u91cd\u5438\u6536 *\/\r\n\r\n    for (int i=l-1;i>=2;i--){\r\n        for (size_t j=0;j<layer[i].size();j++){\r\n            int u = layer[i][j];\r\n            if (excess[u] == 0) continue;\r\n            if (excess[u] > 0){\r\n                for (size_t k=0;k<reverse_adj[u].size();k++){\r\n                    edge &#038;arc = E[reverse_adj[u][k]], &#038;rev = E[_r(reverse_adj[u][k])];\r\n                    if (arc.c != 0){\r\n                        if (excess[u]<arc.c){\r\n                            rev.c += excess[u]; arc.c -= excess[u];\r\n                            excess[arc.v] += excess[u]; excess[u] = 0;\r\n                            break;\r\n                        }\r\n                        else {\r\n                            excess[u] -= arc.c; excess[arc.v] += arc.c;\r\n                            rev.c += arc.c; arc.c = 0;\r\n                        }\r\n                    }\r\n                }\r\n\r\n                \/\/if (excess[u]!=0) cout << 1\/0 << endl;\r\n            }\r\n            else {\r\n                for (size_t k=0;k<reverse_adj[u].size();k++){\r\n                    edge &#038;arc = E[reverse_adj[u][k]], &#038;rev = E[_r(reverse_adj[u][k])];\r\n                    if (rev.c != 0){\r\n                        if (rev.c + excess[u] >= 0){\r\n                            rev.c += excess[u]; arc.c -= excess[u];\r\n                            excess[arc.v] += excess[u]; excess[u] = 0;\r\n                            break;\r\n                        }\r\n                        else {\r\n                            excess[u] -= arc.c; excess[arc.v] += arc.c;\r\n                            rev.c += arc.c; arc.c = 0;\r\n                        }\r\n                    }\r\n                }\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\nint main(){\r\n    \/\/int T; cin >> T;\r\n    \/\/for (int i=0;i<T;i++){\r\n        \/\/if (i!=0) printf(\"\\n\");\r\n        init();  Dinitz(); print();\r\n    \/\/}\r\n}\r\n<\/pre>\n<h3>External link :<\/h3>\n<p><a href=\"http:\/\/www.answeror.com\/archives\/28940\">[ZJU][2364][Data Transmission]     Helanic Abyss<\/a><br \/>\n<a href=\"http:\/\/watashi.ws\/blog\/970\/andrew-stankevich-3-solution\/\">Andrew Stankevich\u2019s Contest #3\u89e3\u9898\u62a5\u544a by watashi<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u7ed9\u5b9a\u4e00\u5f20\u5206\u5c42\u56fe\uff0c\u6c42\u4e00\u6b21\u963b\u585e\u6d41&#8230;<\/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-117","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1T","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/117","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=117"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/117\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}