{"id":126073,"date":"2020-01-13T23:12:40","date_gmt":"2020-01-13T15:12:40","guid":{"rendered":"http:\/\/4563.org\/?p=126073"},"modified":"2020-01-13T23:12:40","modified_gmt":"2020-01-13T15:12:40","slug":"%e8%af%b7%e6%95%99%e4%b8%80%e9%81%93%e5%85%b3%e4%ba%8e%e5%ad%90%e6%a0%91%ef%bc%88%e5%9b%be%ef%bc%89%e5%8c%b9%e9%85%8d%e7%9a%84-oj-%e9%a2%98","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=126073","title":{"rendered":"\u8bf7\u6559\u4e00\u9053\u5173\u4e8e\u5b50\u6811\uff08\u56fe\uff09\u5339\u914d\u7684 OJ \u9898"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u8bf7\u6559\u4e00\u9053\u5173\u4e8e\u5b50\u6811\uff08\u56fe\uff09\u5339\u914d\u7684 OJ \u9898               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : fourstring <\/span>  <span><i><\/i> 54<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<p>\u9898\u76ee\u539f\u6587\u5982\u4e0b\uff1a<\/p>\n<h2>Description<\/h2>\n<p>\u7ed9\u5b9a\u4e24\u68f5\u65e0\u6839\u6811\uff0c\u95ee\u7b2c\u4e00\u68f5\u6811\u662f\u5426\u5305\u542b\u7b2c\u4e8c\u68f5\u6811\u3002<\/p>\n<h2>Input Format<\/h2>\n<p>\u6b64\u9898\u4ec5\u6709\u4e00\u4e2a\u6d4b\u8bd5\u70b9\uff0c<\/p>\n<p>\u591a\u7ec4\u6570\u636e\uff0c\u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6570\u8868\u793a\u6570\u636e\u7ec4\u6570\u3002<\/p>\n<p>\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff1a<\/p>\n<p>\u7b2c\u4e00\u884c\u4e3a N \u8868\u793a\u7b2c\u4e00\u68f5\u6811\u7684\u70b9\u6570<\/p>\n<p>\u63a5\u4e0b\u6765 N-1 \u884c\u63cf\u8ff0\u7b2c\u4e00\u68f5\u6811\u7684\u8fb9<\/p>\n<p>\u63a5\u4e0b\u6765\u4e00\u884c\u4e3a M \u8868\u793a\u7b2c\u4e8c\u68f5\u6811\u7684\u70b9\u6570<\/p>\n<p>\u63a5\u4e0b\u6765 M-1 \u884c\u63cf\u8ff0\u7b2c\u4e8c\u68f5\u6811\u7684\u8fb9<\/p>\n<h2>Output Format<\/h2>\n<p>\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u82e5\u7b2c\u4e00\u68f5\u6811\u5305\u542b\u7b2c\u4e8c\u68f5\u6811\u5219\u8f93\u51fa YES \u5426\u5219\u8f93\u51fa NO<\/p>\n<h2>Sample Input<\/h2>\n<pre><code>2 5 1 2 1 3 3 4 3 5 4 1 4 2 4 3 4 4 1 2 1 3 1 4 4 1 2 2 3 3 4 <\/code><\/pre>\n<h2>Sample Output<\/h2>\n<pre><code>YES NO <\/code><\/pre>\n<h2>Hint<\/h2>\n<p>n,m&lt;=100 \uff1b 150 \u7ec4\u6570\u636e<\/p>\n<p>\u8fd9\u9898\u548c\u4e00\u822c\u5b50\u6811\u5339\u914d\u95ee\u9898\u4e0d\u540c\u7684\u5730\u65b9\u5728\u4e8e\u8f93\u5165\u6570\u636e\u7684\u683c\u5f0f\uff0c\u9996\u5148\u8f93\u5165\u7684\u6811\u662f\u65e0\u6839\u7684\uff0c\u5b9e\u9645\u4e0a\u76f8\u5f53\u4e8e\u4e00\u4e2a\u56fe\u7684\u751f\u6210\u6811\uff1b\u5176\u6b21\u4e24\u68f5\u6811\u4e4b\u95f4\u7ed3\u70b9\u7684\u5bf9\u5e94\u5173\u7cfb\u5e76\u6ca1\u6709\u7ed9\u5b9a\uff0c\u6240\u4ee5\u65e0\u6cd5\u901a\u8fc7\u7b80\u5355\u524d\u5e8f+\u4e2d\u5e8f\u904d\u5386\u6bd4\u8f83\u7684\u65b9\u5f0f\u6765\u786e\u5b9a\u7b2c\u4e00\u68f5\u6811\u662f\u5426\u5305\u542b\u4e86\u7b2c\u4e8c\u68f5\u6811\u3002<\/p>\n<p>\u4ece\u56fe\u7684\u89d2\u5ea6\u6765\u770b\u8fd9\u4f3c\u4e4e\u662f\u4e00\u4e2a\u5b50\u56fe\u5339\u914d(Subgraph Matching)\u95ee\u9898\uff0c\u67e5\u4e86\u4e0b Google \u53ea\u627e\u5230\u4e86\u4e00\u4e9b\u5173\u4e8e\u5b50\u56fe\u540c\u6784(Subgraph isomorphism)\u7684\u8d44\u6599\uff0c\u5982 Ullmann \u7b97\u6cd5\u548c VF2 \u7b97\u6cd5\uff0c\u4f46\u5b83\u4eec\u90fd\u8981\u6c42\u4e24\u56fe\u4e4b\u95f4\u7ed3\u70b9\u7684\u6620\u5c04\u662f\u7ed9\u5b9a\u7684\uff0c\u4f46\u4e8b\u5b9e\u4e0a\u5bf9\u4e8e\u672c\u9898\u5982\u679c\u80fd\u627e\u5230\u8fd9\u6837\u4e00\u4e2a\u6620\u5c04\u5173\u7cfb\uff0c\u5269\u4e0b\u7684\u4e5f\u5e76\u4e0d\u6210\u4e3a\u95ee\u9898\u3002<\/p>\n<p>\u53e6\u5916\u6211\u8fd8\u627e\u5230\u4e86\u672c\u9898\u7684\u4e00\u4efd AC \u4ee3\u7801\uff0c\u4e0d\u8fc7\u5e26\u6709\u660e\u663e\u7684 OI \u98ce\u683c\uff0c\u7531\u4e8e\u6211\u4e2a\u4eba\u6ca1\u6709\u76f8\u5173\u7ecf\u9a8c\u6240\u4ee5\u8c03\u8bd5\u4e86\u5f88\u4e45\u4e5f\u6ca1\u7406\u89e3\u8fd9\u6bb5\u4ee3\u7801\u7684\u5199\u6cd5\uff0c\u94fe\u63a5\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li>https:\/\/git.codingcafe.org\/Contest\/SJTUOJ\/blob\/0c4dde00abbdcc0933118e9622c66b7a76231cb5\/P1314\/SJTUOJ_P1314.cpp<\/li>\n<\/ul>\n<p>\u8bf7\u95ee\u662f\u5426\u6709\u5927\u4f6c\u6307\u70b9\u4e00\u4e0b\u672c\u9898\u7684\u7b80\u5355\u601d\u8def\u6216\u8005\u80fd\u5927\u81f4\u89e3\u91ca\u4e00\u4e0b\u8fd9\u6bb5 AC \u4ee3\u7801\u7684\u903b\u8f91\uff1f\u611f\u6fc0\u4e0d\u5c3d\uff01<\/p>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u8bf7\u6559\u4e00\u9053\u5173\u4e8e\u5b50\u6811\uff08\u56fe\uff09\u5339\u914d\u7684 OJ&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/126073"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=126073"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/126073\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=126073"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=126073"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=126073"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}