{"id":122,"date":"2010-08-16T08:33:15","date_gmt":"2010-08-16T00:33:15","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=122"},"modified":"2012-03-03T08:33:30","modified_gmt":"2012-03-03T00:33:30","slug":"rqnoj-306-%e7%a0%b4%e5%9d%8f%e7%9f%b3%e6%b2%b9%e8%bf%90%e8%be%93%e7%b3%bb%e7%bb%9f%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/rqnoj-306-%e7%a0%b4%e5%9d%8f%e7%9f%b3%e6%b2%b9%e8%bf%90%e8%be%93%e7%b3%bb%e7%bb%9f%e9%97%ae%e9%a2%98\/","title":{"rendered":"RQNOJ 306. \u7834\u574f\u77f3\u6cb9\u8fd0\u8f93\u7cfb\u7edf\u95ee\u9898"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u5bfb\u627e\u54ea\u4e9b\u8fb9\u7684\u5220\u9664\u4f1a\u5f71\u54cd\u6700\u5927\u6d41\u6d41\u91cf\u3002<br \/>\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>\uff08\u6211\u4e4b\u524d\u60f3\u7684\u65b9\u6cd5\u4e00\u76f4\u662f\u626b\u63cf\u6bcf\u4e00\u6761\u8fb9\u662f\u5426\u9971\u548c\u3002\u3002\u4e0d\u8fc7\u8fd9\u4e2a\u60f3\u6cd5\u592a\u66b4\u529b\u4e86\u3002\u3002\u56e0\u4e3a\u4f1a\u5b58\u5728\u53ef\u4ee5\u4ece\u5176\u4ed6\u5730\u65b9\u7ed5\u8fc7\u8fd9\u6761\u8fb9\u800c\u4ea7\u751f\u540c\u6837\u6548\u679c\u7684\u8def\u5f84\u3002\uff09<\/p>\n<p>\u3002\u3002\u3002Dinic \u5b8c\u4ee5\u540e\uff0c\u7528 Floyd \u6c42\u6b8b\u91cf\u7f51\u7edc\u7684\u4f20\u9012\u95ed\u5305\u3002<br \/>\n\u6ce8\u610f\u5224\u65ad\u8fb9\u7684\u65f6\u5019\u8981\u4e24\u4e2a\u65b9\u5411\u540c\u65f6\u5440\u3002<\/p>\n<pre lang=\"cpp\">\r\n\/*\r\n    ID: xiaodao\r\n    PROG: RQ 306. \u7834\u574f\u77f3\u6cb9\u8fd0\u8f93\u7cfb\u7edf\u95ee\u9898\r\n    TAGS: Network-Flow\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <vector>\r\nusing namespace std;\r\nconst int INF = 1000000;\r\nconst int N = 131, M = N*(N-1)\/2;\r\nstruct edge{\r\n    int x, y;\r\n};\r\nstruct rec{\r\n    int v, p, k;\r\n}; \/\/ Stack type\r\nint C[N][N]; \/\/ Residual graph ..\r\nint L[N]; edge E[M]; \/\/ Leval label ... Edge content.\r\nint n, m, s, t;\r\n\r\n\r\n\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; C[u][v] != 0){\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                    C[u][v] -= delta;\r\n                    C[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] == 0) continue; \/\/#\r\n                if (L[u] + 1 == 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]  < stack[top-1].k){\r\n                    stack[top].k = C[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}\r\n\r\nvoid solve(){\r\n    bool G[n+1][n+1];\r\n\r\n    for (int i=1;i<=n;i++)\r\n        for (int j=1;j<=n;j++)\r\n            G[i][j] = (C[i][j] != 0);\r\n\r\n    for (int k=1;k<=n;k++)\r\n        for (int i=1;i<=n;i++)\r\n            for (int j=1;j<=n;j++)\r\n                G[i][j] = G[i][j] || (G[i][k] &#038;&#038; G[k][j]);\r\n\r\n    vector<int> list;\r\n    for (int i=1;i<=m;i++)\r\n        if (!G[E[i].x][E[i].y] || !G[E[i].y][E[i].x]) list.push_back(i);\r\n\r\n    cout << list.size() << endl;\r\n    for (int i=0;i<list.size();i++)\r\n        cout << list[i] << endl;\r\n}\r\n\r\n\r\n\/\/ regularization ... Because My dinic regard source and sink as default 1 &#038;&#038; n ..\r\nvoid r(int &#038;x){\r\n    if (x==1) x = s;\r\n    else if (x==s) x = 1;\r\n    else if (x==n) x = t;\r\n    else if (x==t) x = n;\r\n}\r\n\r\n\r\nvoid init(){\r\n    memset(C, 0, sizeof(C));\r\n    int c;\r\n    cin >> n >> m >> s >> t;\r\n    for (int i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\", &#038;E[i].x, &#038;E[i].y, &#038;c);\r\n        r(E[i].x); r(E[i].y);\r\n        C[E[i].x][E[i].y] += c;\r\n        C[E[i].y][E[i].x] += c;\r\n    }\r\n}\r\n\r\n\r\n\r\nint main(){\r\n    init(); dinic();\r\n    solve();\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u5bfb\u627e\u54ea\u4e9b\u8fb9\u7684\u5220\u9664\u4f1a\u5f71\u54cd\u6700\u5927\u6d41\u6d41\u91cf\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-122","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1Y","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/122","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=122"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/122\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}