{"id":116,"date":"2010-08-22T08:29:50","date_gmt":"2010-08-22T00:29:50","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=116"},"modified":"2012-03-03T08:30:07","modified_gmt":"2012-03-03T00:30:07","slug":"poj-3469-dual-core-cpu","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-3469-dual-core-cpu\/","title":{"rendered":"POJ 3469. Dual Core CPU"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u7ed9\u5b9a n \u4e2a\u8fdb\u7a0b\u5728\u4e24\u4e2a\u4e0d\u540c\u7684\u6838\u5fc3\u4e0a\u8fd0\u884c\u7684\u4ee3\u4ef7ai, bi\uff0c\u4e00\u4e9b\u8fdb\u7a0b\u4e4b\u95f4\u53ef\u80fd\u5b58\u5728\u8054\u7cfb\uff0c\u7ed9\u5b9a m \u4e2a\u8fd9\u6837\u7684\u4e09\u5143\u7ec4 (xi, yi, ci)\uff0c\u5982\u679c xi, yi \u4e0d\u80fd\u5728\u540c\u4e00\u4e2a\u6838\u5fc3\u4e0a\u8fd0\u884c\u5219\u4f1a\u4ea7\u751f\u989d\u5916\u7684 ci \u4efd\u8f6c\u79fb\u4ee3\u4ef7\uff0c\u6c42\u6700\u5c0f\u3002<\/p>\n<p><!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>\u6211\u5199\u4e00\u4e9b\u522b\u7684\u5427\u3002\u3002\u3002\u611f\u89c9\u8fd9\u4e9b\u5e94\u7528\u6700\u5c0f\u5272\u6c42\u89e3\u7684\u9898\u3002\u3002\u6211\u603b\u662f\u559c\u6b22\u786c\u4ece\u6700\u5927\u6d41\u7684\u65b9\u5411\u5f00\u59cb\u601d\u8003\u3002\u3002\u7ed3\u679c\u5f80\u5f80\u662f\u60f3\u4e86\u597d\u591a\u65f6\u95f4\u3002\u3002\u4f24\u5bb3\u4e86\u597d\u591a\u8111\u7ec6\u80de\u3002<\/p>\n<p>\u8fd8\u6709\uff0c\u8bbe\u5b9a\u5e38\u91cf\u7684\u65f6\u5019\uff0c\u6211\u603b\u662f\u559c\u6b22\u7b97\u7684\u5f88\u4ed4\u7ec6\uff0c\u8ba9\u7a7a\u95f4\u4e00\u4efd\u4e5f\u4e0d\u591a\uff0c\u4e4b\u524d\u4e00\u76f4 Runtime Error\uff0c\u600e\u4e48\u6539\u90fd\u4e0d\u5bf9\uff0c\u4e00\u6012\u4e4b\u4e0b\u770b\u4e86\u4eba\u5bb6\u7684\u6807\u7a0b\uff0c\u53d1\u73b0\u4ed6\u628a M \u8bbe\u5b9a\u6210 50W\uff0c\u4e8e\u662f\u6211\u4e5f\u8bbe\u5b9a\u6210 50 W\uff0cAC &#8230; \uff087000ms+\uff09<\/p>\n<pre lang=\"cpp\" file=\"POJ_3469.cpp\">\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <vector>\r\nusing namespace std;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 20001, M =  500000;\r\nstruct edge{\r\n    int v, c;\r\n    void insert(int, int);\r\n};\r\n\r\nstruct node{\r\n    vector<int> adj;\r\n    int D;\r\n};\r\n\r\nstruct network_flow{\r\n    node V[N+1]; edge E[M+1];\r\n    int edge_count, max_flow;\r\n    int n, m, s, t;\r\n    void init();\r\n    void add_edge(int, int, int);\r\n    void bfs();\r\n    void Dinitz();\r\n};\r\n\r\ninline int _r(int x){\r\n    return x ^ 1;\r\n}\r\n\r\n\r\nvoid edge::insert(int a, int b){\r\n    v = a; c = b;\r\n};\r\n\r\nvoid network_flow::add_edge(int x, int y, int c){\r\n    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, c);\r\n}\r\n\r\nvoid network_flow::bfs(){\r\n    int Q[N+1] = {s}, head = 0, tail = 1;\r\n    for (int i=1;i<=n;i++) V[i].D = -1; \/\/memset(V.D, -1, sizeof(V.D));\r\n    V[s].D = 0;\r\n\r\n    int u;\r\n    while (head<tail){\r\n        u = Q[head];\r\n        for (size_t i=0;i<V[u].adj.size();i++){\r\n            edge &#038;arc = E[V[u].adj[i]];\r\n            if (V[arc.v].D==-1 &#038;&#038; arc.c!=0){\r\n                Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;\r\n                if (arc.v == t) return;\r\n                tail++;\r\n            }\r\n        }\r\n        head++;\r\n    }\r\n}\r\n\r\nvoid network_flow::Dinitz(){\r\n    max_flow = 0;\r\n\r\n    bfs();\r\n    while (V[t].D!=-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            if (u == t){\r\n                int delta = INF, handle;\r\n                for (int i=1;i<=top;i++){\r\n                    edge &#038;arc = E[stack[i]];\r\n                    if (arc.c < delta){\r\n                        delta = arc.c;\r\n                        handle = i;\r\n                    }\r\n                }\r\n                max_flow += delta;\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                \/*\r\n                for (int i=handle;i<=top;i++){\r\n                    cur[stack[i]] = 0;\r\n                } *\/\r\n\r\n                top = handle-1;\r\n                continue;\r\n            }\r\n\r\n            for (i=cur[u];i<V[u].adj.size();i++){\r\n                edge &#038;arc = E[V[u].adj[i]];\r\n                if (V[arc.v].D == V[u].D + 1 &#038;&#038; arc.c!=0) break;\r\n            }\r\n\r\n            if (i == V[u].adj.size()){\r\n                V[u].D = -1, top--;\r\n            }\r\n            else {\r\n                cur[u] = i + 1;\r\n                stack[++top] = V[u].adj[i];\r\n            }\r\n        }\r\n        bfs();\r\n    }\r\n}\r\n\r\n\r\n\r\nvoid network_flow::init(){\r\n    for (int i=0;i<=N;i++) V[i].adj.clear();\r\n    edge_count = 0;\r\n}\r\n\r\nvoid input(network_flow &#038;G){\r\n    G.init();\r\n\r\n    G.s = 0; G.t = G.n + 1;\r\n    G.E[M].v = G.s;\r\n\r\n    int x, y, c;\r\n    for (int i=1;i<=G.n;i++){\r\n        scanf(\"%d%d\", &#038;x, &#038;y);\r\n        G.add_edge(G.s, i, x); G.add_edge(i, G.s, 0);\r\n        G.add_edge(i, G.t, y); G.add_edge(G.t, i, 0);\r\n    }\r\n\r\n    G.n++;\r\n\r\n    for (int i=1;i<=G.m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;c);\r\n        G.add_edge(x, y, c);\r\n        G.add_edge(y, x, c);\r\n    }\r\n}\r\n\r\nnetwork_flow G;\r\n\r\nint main(){\r\n    while (scanf(\"%d%d\", &#038;G.n, &#038;G.m) == 2){\r\n        input(G); G.Dinitz();\r\n        cout << G.max_flow << endl;\r\n    }\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n<\/pre>\n<h3>External link :<\/h3>\n<p>http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3469<br \/>\nhttp:\/\/www.answeror.com\/archives\/27504<br \/>\nhttp:\/\/hi.baidu.com\/gugugupan\/blog\/item\/04f2e81aa6a969fdaf513381.html<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u7ed9\u5b9a n \u4e2a\u8fdb\u7a0b\u5728\u4e24\u4e2a\u4e0d\u540c\u7684\u6838\u5fc3\u4e0a\u8fd0\u884c\u7684\u4ee3\u4ef7ai, bi\uff0c\u4e00\u4e9b\u8fdb\u7a0b\u4e4b\u95f4\u53ef\u80fd\u5b58\u5728\u8054\u7cfb\uff0c\u7ed9\u5b9a m \u4e2a\u8fd9\u6837\u7684\u4e09\u5143\u7ec4 (xi, yi, ci)\uff0c\u5982\u679c xi, yi \u4e0d\u80fd\u5728\u540c\u4e00\u4e2a\u6838\u5fc3\u4e0a\u8fd0\u884c\u5219\u4f1a\u4ea7\u751f\u989d\u5916\u7684 ci \u4efd\u8f6c\u79fb\u4ee3\u4ef7\uff0c\u6c42\u6700\u5c0f\u3002<\/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-116","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1S","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/116","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=116"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/116\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}