{"id":494,"date":"2013-08-20T20:52:42","date_gmt":"2013-08-20T12:52:42","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=494"},"modified":"2013-08-20T20:52:42","modified_gmt":"2013-08-20T12:52:42","slug":"1053-path-of-equal-weight-30","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=494","title":{"rendered":"1053. Path of Equal Weight (30)"},"content":{"rendered":"<p>\u539f\u9898\u94fe\u63a5\uff1a<a href=\"http:\/\/pat.zju.edu.cn\/contests\/pat-a-practise\/1053\">http:\/\/pat.zju.edu.cn\/contests\/pat-a-practise\/1053<\/a><br \/>\n\u8fd9\u9053\u9898\u76ee\u5c31\u662f\u4e2a\u6811\u7684\u904d\u5386\uff0c\u53cd\u6b63\u6811\u561b\u53ef\u4ee5\u597d\u591a\u65b9\u6cd5\u6784\u9020\u7684&#8230;\u6211\u8fd9\u8fb9\u5c31\u7ed9\u4e86\u4e2amap\u5b9e\u73b0\uff0c\u5176\u5b9e\u7528\u6570\u7ec4\u4e5f\u662f\u5b8c\u5168\u53ef\u4ee5\u7684\u561b:)<br \/>\n\u7136\u540e\u4e0d\u7ba1\u7528DFS,BFS\u8fd8\u662f\u795e\u9a6c\u904d\u5386\u4e00\u4e0b\u6574\u68f5\u6811\u5c31\u51fa\u6765\u4e86&#8230;<br \/>\n\u80fd\u7ee7\u7eed\u4f7f\u7528\u7684\u5728working\u91cc\u9762\uff0c\u6709\u7ed3\u679c\u7684\u5728result\u91cc\u9762<br \/>\n\u4e00\u5f00\u59cbworking\u96c6\u5408\u653e\u4e00\u4e2a\u6839\u8282\u70b9\u7684Path<br \/>\n\u6ce8\u610f\u7279\u6b8a\u60c5\u51b5\uff1a\u53ea\u6709\u6839\u8282\u70b9\u4e00\u4e2a\u8282\u70b9\u7684\u65f6\u5019&#8230;.<br \/>\n\u5176\u4ed6\u6ca1\u5565\u7279\u522b\u7684\uff0c\u539f\u4ee5\u4e3a10ms\u65f6\u95f4\u5f88\u77ed\uff0c\u505a\u51fa\u6765\u624d\u53d1\u73b0\u5176\u5b9e\u90fd\u662f0ms\u641e\u5b9a\u7684:)<br \/>\n\u53e6\u5916\u53e6\u5916\uff0c\/\/\u6389\u7684\u7ed3\u6784\u5185\u7684\u8fd0\u7b97\u7b26\u91cd\u8f7d\uff0cVS2013\u53ef\u4ee5\u8fd0\u884c\uff0c\u4f46\u662fPAT\u51fa\u73b0\u7f16\u8bd1\u9519\u8bef\uff0c\u8c8c\u4f3c\u662flinux\u4e0b\u4e25\u683c\u4e00\u4e9b\u7684\u5427\uff0c\u7701\u4e8b\u513f\u5c31\u6539\u6210\u4e86\u5916\u9762\u81ea\u5b9a\u4e49\u6bd4\u8f83\u51fd\u6570\u4e86\u3002\u636e\u67e5\uff0c\u7ed3\u6784\u4f53\u5185\u641e\u4e2a\u53cb\u5143\u51fd\u6570\u7136\u540e\u7ed3\u6784\u4f53\u5916\u9762\u5199\u5b9e\u73b0\u4e5f\u662f\u53ef\u4ee5\u7684&#8230;\u4e0d\u8fc7\u8fd9\u6837\u597d\u9ebb\u70e6<br \/>\n&nbsp;<\/p>\n<pre>\n#include <stdio.h>\n#include <string>\n#include <map>\n#include <deque>\n#include <vector>\n#include <list>\n#include <algorithm>\nusing namespace std;\nint *weight;\nstruct Path\n{\n    list path;\n    long currWt;\n    Path()\n    {\n        currWt = 0;\n    }\n    \/\/\/\/\u91cd\u8f7d\u8fd0\u7b97\u7b26\u5b9e\u73b0sort\n    \/\/bool operator &lt;(const Path&amp; p2)\n    \/\/{\n    \/\/    list::const_iterator it1 = path.begin();\n    \/\/    list::const_iterator it2 = p2.path.begin();\n    \/\/    while(it1 != path.end() &amp;&amp; it2 != p2.path.end())\n    \/\/    {\n    \/\/        int id1 = *it1;\n    \/\/        int wt1 = weight[id1];\n    \/\/        int id2 = *it2;\n    \/\/        int wt2 = weight[id2];\n    \/\/        if(wt2 &gt; wt1)\n    \/\/            return false;\n    \/\/        else if(wt2 &lt; wt1)\n    \/\/            return true;\n    \/\/        it1 ++;\n    \/\/        it2 ++;\n    \/\/    }\n    \/\/    return false;\n    \/\/}\n};\nbool compare (Path x, Path y)\n{\n    list::const_iterator it1 = x.path.begin();\n        list::const_iterator it2 = y.path.begin();\n        while(it1 != x.path.end() &amp;&amp; it2 != y.path.end())\n        {\n            int id1 = *it1;\n            int wt1 = weight[id1];\n            int id2 = *it2;\n            int wt2 = weight[id2];\n            if(wt2 &gt; wt1)\n                return false;\n            else if(wt2 &lt; wt1)\n                return true;\n            it1 ++;\n            it2 ++;\n        }\n        return false;\n}\n#define PAIR pair&lt;int, vector&gt;\nint main()\n{\n    int N, M;\n    long S;\n    scanf(\"%d %d %ld\", &amp;N, &amp;M, &amp;S);\n    weight = new int[N]; \/\/weights\n    bool *isLeaf = new bool[N];\n    for(int i=0; i&lt;N; i++)\n        isLeaf[i] = true;\n    map&lt;int, vector&gt; tree;\n    vector results;\n    vector working;\n    for(int i=0; i&lt;N; i++)\n    {\n        \/\/read weight\n        scanf(\"%d\", &amp;weight[i]);\n    }\n    for(int i=0; i&lt;M; i++)\n    {\n        \/\/read link info\n        int nodeid;\n        int K;\n        scanf(\"%d %d\", &amp;nodeid, &amp;K);\n        isLeaf[nodeid] = false;\n        vector linkedNodes;\n        while(K--)\n        {\n            int dst;\n            scanf(\"%d\", &amp;dst);\n            linkedNodes.push_back(dst);\n        }\n        tree.insert(PAIR(nodeid, linkedNodes));\n    }\n    \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n    \/\/BFS root id = 00\n    int wt_root = weight[0]; \/\/\u6839\u8282\u70b9\u7684\u6743\u91cd\n    Path path;\n    path.currWt  = wt_root;\n    path.path.push_back(0);\n    working.push_back(path);\n    while(!working.empty())\n    {\n        Path path = working.front(); \/\/\u53d6\u6700\u9876\u4e0a\u4e00\u4e2a\u64cd\u4f5c\n        int lastNode = path.path.back();\n        int currWt = path.currWt; \/\/\u5f53\u524d\u7684\u6743\u91cd\n        if(currWt == S)\n        {\n            \/\/\u521a\u597d\u4e86\u5df2\u7ecf..(\u6839\u8282\u70b9\u5c31\u6ee1\u8db3))\n            results.push_back(path);\n            working.erase(working.begin());\n            continue;\n        }\n        vector linkedNodes = tree[lastNode];\n        vector::iterator it;\n        for(it = linkedNodes.begin(); it!=linkedNodes.end(); it++)\n        {\n            \/\/\u904d\u5386\u6240\u6709\u5b50\u8282\u70b9\n            int id = *it;\n            int wt_till_this = weight[id] + currWt;\/\/\u52a0\u4e0a\u4e4b\u540e\u7684\u6743\u91cd\n            if(wt_till_this &gt; S)\n                continue; \/\/\u5df2\u7ecf\u8d85\u8fc7\u4e86\n            else if(wt_till_this == S)\n            {\n                \/\/\u521a\u597d\uff0c\u52a0\u5165result\u96c6\u5408\n                \/\/\u5982\u679c\u8fd8\u6ca1\u5230\u53f6\u8282\u70b9\uff0c\u90a3\u4e48\u5b83\u4e5f\u4e0d\u662f\u7b54\u6848!\n                if(!isLeaf[id])\n                    continue;\n                Path newPath = path;\n                newPath.currWt = wt_till_this;\n                newPath.path.push_back(id);\n                results.push_back(newPath);\n            }\n            else\n            {\n                \/\/\u867d\u7136\u8fd8\u662f\u5c0f\u4e86\uff0c\u4f46\u662f\u6709\u5e0c\u671b\n                Path newPath = path;\n                newPath.currWt = wt_till_this;\n                newPath.path.push_back(id);\n                working.push_back(newPath);\n            }\n        }\n        \/\/\u4f7f\u7528\u5b8c\u4e86\u4e4b\u540e\uff0c\u5220\u6389\u8fd9\u4e2a\n        working.erase(working.begin());\n    }\n    \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n    \/\/SORT\n    sort(results.begin(), results.end(), compare);\n    \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n    \/\/OUTPUT\n    vector::iterator it;\n    for(it = results.begin(); it != results.end(); it++)\n    {\n        Path p = *it;\n        list::iterator iter;\n        for(iter = p.path.begin(); iter != p.path.end(); iter++)\n        {\n            int id = *iter;\n            int wt = weight[id];\n            if(iter != p.path.begin())\n                printf(\" \");\n            printf(\"%d\", wt);\n        }\n        printf(\"n\");\n    }\n    return 0;\n}\n<\/map><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u9898\u94fe\u63a5\uff1ahttp:\/\/pat.zju.edu.cn\/contests\/pat-a-practise\/1053 \u8fd9\u9053\u9898\u76ee\u5c31\u662f\u4e2a\u6811\u7684\u904d\u5386\uff0c\u53cd\u6b63\u6811\u561b\u53ef\u4ee5\u597d\u591a\u65b9\u6cd5\u6784\u9020\u7684&#8230;\u6211\u8fd9\u8fb9\u5c31\u7ed9\u4e86\u4e2amap\u5b9e\u73b0\uff0c\u5176\u5b9e\u7528\u6570\u7ec4\u4e5f\u662f\u5b8c\u5168\u53ef\u4ee5\u7684\u561b:) \u7136\u540e\u4e0d\u7ba1\u7528DFS,BFS\u8fd8\u662f\u795e\u9a6c\u904d\u5386\u4e00\u4e0b\u6574\u68f5\u6811\u5c31\u51fa\u6765\u4e86&#8230; \u80fd\u7ee7\u7eed\u4f7f\u7528\u7684\u5728working\u91cc\u9762\uff0c\u6709\u7ed3\u679c\u7684\u5728result\u91cc\u9762 \u4e00\u5f00\u59cbworking\u96c6\u5408\u653e\u4e00\u4e2a\u6839\u8282\u70b9\u7684Path \u6ce8\u610f\u7279\u6b8a\u60c5\u51b5\uff1a\u53ea\u6709\u6839\u8282\u70b9\u4e00\u4e2a\u8282\u70b9\u7684\u65f6\u5019&#8230;. \u5176\u4ed6\u6ca1\u5565\u7279\u522b\u7684\uff0c\u539f\u4ee5\u4e3a10ms\u65f6\u95f4\u5f88\u77ed\uff0c\u505a\u51fa\u6765\u624d\u53d1\u73b0\u5176\u5b9e\u90fd\u662f0ms\u641e\u5b9a\u7684:) \u53e6\u5916\u53e6\u5916\uff0c\/\/\u6389\u7684\u7ed3\u6784\u5185\u7684\u8fd0\u7b97\u7b26\u91cd\u8f7d\uff0cVS2013\u53ef\u4ee5\u8fd0\u884c\uff0c\u4f46\u662fPAT\u51fa\u73b0\u7f16\u8bd1\u9519\u8bef\uff0c\u8c8c\u4f3c\u662flinux\u4e0b\u4e25\u683c\u4e00\u4e9b\u7684\u5427\uff0c\u7701\u4e8b\u513f\u5c31\u6539\u6210\u4e86\u5916\u9762\u81ea\u5b9a\u4e49\u6bd4\u8f83\u51fd\u6570\u4e86\u3002\u636e\u67e5\uff0c\u7ed3\u6784\u4f53\u5185\u641e\u4e2a\u53cb\u5143\u51fd\u6570\u7136\u540e\u7ed3\u6784\u4f53\u5916\u9762\u5199\u5b9e\u73b0\u4e5f\u662f\u53ef\u4ee5\u7684&#8230;\u4e0d\u8fc7\u8fd9\u6837\u597d\u9ebb\u70e6 &nbsp; #include #include #include #include #include #include #include using namespace std; int *weight; struct Path { list path; long currWt; Path() { currWt = 0; } \/\/\/\/\u91cd\u8f7d\u8fd0\u7b97\u7b26\u5b9e\u73b0sort \/\/bool operator &lt;(const Path&amp; p2) \/\/{ \/\/ list::const_iterator it1 = path.begin(); \/\/ list::const_iterator it2 = p2.path.begin(); \/\/ while(it1 != path.end() [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-494","post","type-post","status-publish","format-standard","hentry","category-study"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/494","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=494"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/494\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=494"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=494"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=494"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}