{"id":105,"date":"2010-09-09T09:23:49","date_gmt":"2010-09-09T01:23:49","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=105"},"modified":"2012-03-03T19:35:34","modified_gmt":"2012-03-03T11:35:34","slug":"zoj-2676-network-wars","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/zoj-2676-network-wars\/","title":{"rendered":"ZOJ 2676. Network Wars"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6d41\u7f51\u7edc\uff0c\u9009\u53d6\u4e00\u4e2a\u5305\u542b\u5272\u7684\u8fb9\u96c6E\uff0c\u4f7f\u5f97\u8fb9\u6743\u7684\u5e73\u5747\u503c\u6700\u5c0f\u3002<br \/>\n<!--more--><\/p>\n<pre lang=\"cpp\">\r\n\/*\r\n    Author  : xiaodao\r\n    Problem : ZOJ 2676. Network Wars\r\n    Status  : Accepted\r\n    Last Modify : GMT +8. Sept 9th 14:48.\r\n    Tags : 0\/1\u5206\u6570\u89c4\u5212\uff0c\u6700\u5c0f\u5272\r\n*\/\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <vector>\r\n#include <cmath>\r\n\r\nusing namespace std;\r\nconst double EPS = 1e-6, INF = 1e9;\r\nconst int N = 500, M = 2000;\r\nstruct edge{\r\n    int v, c; double cc; bool used;\r\n    void insert(int, int);\r\n};\r\nstruct node{\r\n    vector<int> adj;\r\n    int D;\r\n};\r\nstruct network_flow{\r\n    node V[N+1]; edge E[M+1];\r\n    int edge_count; double max_flow, negative_edge;\r\n    int n, m, s, t;\r\n    void init();\r\n    void print();\r\n    void rebuild(double);\r\n    void add_edge(int, int, int);\r\n    void bfs();\r\n    void Dinitz();\r\n};\r\ninline int _r(int x){\r\n    return x ^ 1;\r\n}\r\nvoid edge::insert(int a, int b){\r\n    v = a; c = b; used = false;\r\n};\r\nvoid network_flow::add_edge(int x, int y, int z){\r\n    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, z);\r\n}\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;\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.cc>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                double delta = INF; int handle;\r\n                for (int i=1;i<=top;i++){\r\n                    edge &#038;arc = E[stack[i]];\r\n                    if (arc.cc < delta){\r\n                        delta = arc.cc;\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]].cc -= delta;\r\n                    E[_r(stack[i])].cc += delta;\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.cc>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=1;i<=n;i++) V[i].adj.clear();\r\n    edge_count = 0; s = 1; t = n;\r\n    E[M].v = s;\r\n\r\n    int x, y, z;\r\n    for (int i=0;i<m;i++){\r\n        scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;z);\r\n        add_edge(x, y, z);\r\n        add_edge(y, x, z);\r\n    }\r\n}\r\n\r\nvoid network_flow::rebuild(double x){\r\n    negative_edge = 0;\r\n    for (int i=0;i<m;i++){\r\n        double key = E[2*i].c - x;\r\n        if (key<0){\r\n            negative_edge += key;\r\n            E[2*i].cc = E[2*i+1].cc = 0;\r\n            E[2*i].used = true;\r\n        }\r\n        else{\r\n            E[2*i].cc = E[2*i+1].cc = key;\r\n            E[2*i].used = false;\r\n        }\r\n    }\r\n}\r\n\r\nvoid network_flow::print(){\r\n    for (int i=0;i<m;i++)\r\n        if ( (V[E[2*i].v].D>=0) != (V[E[2*i+1].v].D>=0) )\r\n            E[2*i].used = true;\r\n\r\n    int count = 0;\r\n    for (int i=0;i<m;i++)\r\n        if (E[2*i].used) count++;\r\n    printf(\"%d\\n\", count);\r\n\r\n    for (int i=0;i<m;i++)\r\n        if (E[2*i].used) printf(\"%d \", i+1);\r\n    puts(\"\");\r\n}\r\n\r\n\r\nnetwork_flow G;\r\n\r\ndouble f(double x){\r\n    G.rebuild(x); G.Dinitz();\r\n    return G.max_flow + G.negative_edge;\r\n}\r\n\r\nint main(){\r\n    double l, r, m;\r\n    while (scanf(\"%d %d\", &#038;G.n, &#038;G.m)==2){\r\n        G.init(); l = INF; r = 0;\r\n        for (int i=0;i<G.m;i++)\r\n            l = min(l, double(G.E[i*2].c)), r = max(r, double(G.E[i*2].c));\r\n        l -= EPS; r += EPS; \/\/ @_ @\r\n\r\n        while (l+EPS<r){\r\n            m = (l+r) \/ 2; \/\/if (fabs(f(m))<=EPS) break;  \/\/ Need not ...\r\n            if (f(m) > 0) l = m;\r\n            else r = m;\r\n        }\r\n        G.print();\r\n    }\r\n}\r\n\r\n<\/pre>\n<blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u7ed9\u5b9a\u4e00\u4e2a\u6d41\u7f51\u7edc\uff0c\u9009\u53d6\u4e00\u4e2a\u5305\u542b\u5272\u7684\u8fb9\u96c6E\uff0c\u4f7f\u5f97\u8fb9\u6743\u7684\u5e73\u5747\u503c\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-105","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1H","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/105","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=105"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/105\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=105"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=105"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=105"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}