{"id":417,"date":"2020-05-01T23:55:59","date_gmt":"2020-05-01T15:55:59","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=417"},"modified":"2020-05-02T00:04:25","modified_gmt":"2020-05-01T16:04:25","slug":"%e4%ba%8c%e5%88%86%e5%9b%be%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/01\/%e4%ba%8c%e5%88%86%e5%9b%be%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d\/","title":{"rendered":"\u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d"},"content":{"rendered":"<h3>\u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d<\/h3>\n<p>\u505a\u6cd5\u4e0d\u552f\u4e00\u3002<\/p>\n<h4>\u5308\u7259\u5229\u7b97\u6cd5<\/h4>\n<p>n1\u4e3a\u5de6\u90e8\u5206\u7684\u7ed3\u70b9\uff0cn2\u4e3a\u53f3\uff0cm\u4e3a\u8fb9\u6570\u3002<br \/>\n\u8d2a\u5fc3\u7684\u601d\u60f3\u3002G\u90bb\u63a5\u8868\u5b58\u56fe\uff0c\u4f46\u6ce8\u610f\u8fb9\u662f\u6709\u5411\u8fb9(n1\u6307\u5411n2)\uff0cmatch[i]\u8868\u793a\u53f3\u8fb9\u90e8\u5206\u7684\u7ed3\u70b9\u662f\u5426\u88ab\u5339\u914d\u3002<br \/>\n\u5927\u81f4\u601d\u8def\u5c31\u662f\uff1a\u679a\u4e3en1\u91cc\u7684\u7ed3\u70b9\uff0c\u4e3a\u5b83\u914d\u5bf9\uff0c\u5728n2\u4e2d\u5bfb\u627e\u914d\u5bf9\u70b9\uff0cfind()\u51fd\u6570\u7528\u6765\u5b9e\u73b0\u6b64\u529f\u80fd\uff0c\u82e5\u80fd\u6210\u529f\u914d\u5bf9\uff0c\u8fd4\u56de1\uff1b\u5426\u5219\u8fd4\u56de0\u3002\u679a\u4e3en1\u91cc\u7684\u7ed3\u70b9i\u6240\u6307\u5411\u7684\u6240\u6709\u7ed3\u70b9j\uff0c\u82e5\u8be5\u7ed3\u70b9\u672a\u88ab\u5339\u914d\uff0c\u90a3\u4e48i\u5c31\u5339\u914d\u8fd9\u4e2a\u4e86\uff0c\u8fd4\u56de1\u5373\u53ef\uff1b\u82e5\u8be5\u7ed3\u70b9\u5df2\u7ecf\u88ab\u5339\u914d\u5230\u4e86\uff0c\u5373\u88ab\u5339\u914d\u7684\u7ed3\u70b9\u662fn1\u91cc\u7684match[j]\uff0c\u90a3\u4e48\u518d\u60f3\u529e\u6cd5\u4e3amatch[j]\u5bfb\u627e\u65b0\u7684\u914d\u5bf9\u7ed3\u70b9\uff0c\u82e5\u80fd\u627e\u5230\uff0c\u5219\u4e00\u5207\u7686\u597d\uff0c\uff0c\uff0c\u5426\u5219\u8be5\u7ed3\u70b9\u8df3\u8fc7\uff0c\uff0c\u3002<\/p>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6O(nm)<\/strong><br \/>\n<strong><a href=\"https:\/\/www.acwing.com\/problem\/content\/863\/\">AcWing863 \u4e8c\u5206\u56fe\u7684\u6700\u5927\u5339\u914d<\/a><\/strong><\/p>\n<pre><code class=\"language-c++\">#include &lt;iostream&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int N = 505;\nint n1,n2,m;\nint G[N][N],match[N];\nint st[N];\nbool find(int x){\n    for (int i=1;i&lt;=n2;i++) if (G[x][i] &amp;&amp; !st[i]){\n        st[i] = 1;\n        if (!match[i] || find(match[i])){\n            match[i] = x;\n            return true;\n        }\n    }\n    return false;\n}\nint main(){\n    int a,b;\n    cin &gt;&gt; n1 &gt;&gt; n2 &gt;&gt; m;\n    while (m--){\n        cin &gt;&gt; a &gt;&gt; b;\n        G[a][b] = 1;\n        \/\/G[b][a] = 1;\n    }\n    int res = 0;\n    for (int i=1;i&lt;=n1;i++){\n        memset (st,0,sizeof st);\n        if (find(i))    res++;\n    }\n    cout &lt;&lt; res;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d \u505a\u6cd5\u4e0d\u552f\u4e00\u3002 \u5308\u7259\u5229\u7b97\u6cd5 n1\u4e3a\u5de6\u90e8\u5206\u7684\u7ed3\u70b9\uff0cn2\u4e3a\u53f3\uff0cm\u4e3a\u8fb9\u6570\u3002 \u8d2a\u5fc3\u7684\u601d\u60f3\u3002G\u90bb [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[40],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/417"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=417"}],"version-history":[{"count":5,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/417\/revisions"}],"predecessor-version":[{"id":422,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/417\/revisions\/422"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=417"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=417"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=417"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}