{"id":30907,"date":"2022-10-26T09:04:30","date_gmt":"2023-03-31T00:33:36","guid":{"rendered":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/"},"modified":"2025-08-12T21:20:23","modified_gmt":"2025-08-12T13:20:23","slug":"%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/","title":{"rendered":"\u6700\u5927\u5339\u914d\uff08PHP\uff09"},"content":{"rendered":"<pre class=\"post-pre\"><code>    <span class=\"c1\">\/\/ maximum matching algorithm<\/span>\r\n    <span class=\"c1\">\/\/ unweighted bipartite graph<\/span>\r\n    <span class=\"c1\">\/\/ dfs hungarian algorithm<\/span>\r\n\r\n    <span class=\"k\">function<\/span> <span class=\"n\">dfs<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$u<\/span><span class=\"p\">,<\/span> <span class=\"o\">&amp;<\/span><span class=\"nv\">$path<\/span><span class=\"p\">,<\/span> <span class=\"o\">&amp;<\/span><span class=\"nv\">$matching<\/span><span class=\"p\">){<\/span>\r\n        <span class=\"k\">foreach<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">[<\/span><span class=\"nv\">$u<\/span><span class=\"p\">]<\/span> <span class=\"k\">as<\/span> <span class=\"nv\">$v<\/span><span class=\"p\">){<\/span>\r\n            <span class=\"k\">if<\/span><span class=\"p\">(<\/span><span class=\"o\">!<\/span><span class=\"k\">isset<\/span><span class=\"p\">(<\/span><span class=\"nv\">$path<\/span><span class=\"p\">[<\/span><span class=\"nv\">$v<\/span><span class=\"p\">])){<\/span>      <span class=\"c1\">\/\/ not in path already<\/span>\r\n                <span class=\"nv\">$path<\/span><span class=\"p\">[<\/span><span class=\"nv\">$v<\/span><span class=\"p\">]<\/span> <span class=\"o\">=<\/span> <span class=\"kc\">true<\/span><span class=\"p\">;<\/span>\r\n                <span class=\"k\">if<\/span><span class=\"p\">(<\/span><span class=\"o\">!<\/span><span class=\"k\">isset<\/span><span class=\"p\">(<\/span><span class=\"nv\">$matching<\/span><span class=\"p\">[<\/span><span class=\"nv\">$v<\/span><span class=\"p\">])<\/span> <span class=\"o\">||<\/span> <span class=\"nf\">dfs<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$matching<\/span><span class=\"p\">[<\/span><span class=\"nv\">$v<\/span><span class=\"p\">],<\/span> <span class=\"nv\">$path<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$matching<\/span><span class=\"p\">)){<\/span>\r\n                    <span class=\"c1\">\/\/ not matching node, the path is agumenting path, switch path, and return true<\/span>\r\n                    <span class=\"nv\">$matching<\/span><span class=\"p\">[<\/span><span class=\"nv\">$v<\/span><span class=\"p\">]<\/span> <span class=\"o\">=<\/span> <span class=\"nv\">$u<\/span><span class=\"p\">;<\/span>\r\n                    <span class=\"nv\">$matching<\/span><span class=\"p\">[<\/span><span class=\"nv\">$u<\/span><span class=\"p\">]<\/span> <span class=\"o\">=<\/span> <span class=\"nv\">$v<\/span><span class=\"p\">;<\/span>\r\n                    <span class=\"k\">return<\/span> <span class=\"kc\">true<\/span><span class=\"p\">;<\/span>\r\n                <span class=\"p\">}<\/span>\r\n            <span class=\"p\">}<\/span>\r\n        <span class=\"p\">}<\/span>\r\n\r\n        <span class=\"k\">return<\/span> <span class=\"kc\">false<\/span><span class=\"p\">;<\/span>                   <span class=\"c1\">\/\/ not agumenting path<\/span>\r\n    <span class=\"p\">}<\/span>\r\n\r\n    <span class=\"k\">function<\/span> <span class=\"n\">hungarian<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">){<\/span>\r\n        <span class=\"nv\">$matching<\/span> <span class=\"o\">=<\/span> <span class=\"p\">[];<\/span>\r\n\r\n        <span class=\"k\">foreach<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span> <span class=\"k\">as<\/span> <span class=\"nv\">$u<\/span><span class=\"o\">=&gt;<\/span><span class=\"nv\">$x<\/span><span class=\"p\">){<\/span>\r\n            <span class=\"k\">if<\/span><span class=\"p\">(<\/span><span class=\"o\">!<\/span><span class=\"k\">isset<\/span><span class=\"p\">(<\/span><span class=\"nv\">$matching<\/span><span class=\"p\">[<\/span><span class=\"nv\">$u<\/span><span class=\"p\">])){<\/span>  <span class=\"c1\">\/\/ not a matching node<\/span>\r\n                <span class=\"nv\">$path<\/span> <span class=\"o\">=<\/span> <span class=\"p\">[];<\/span>             <span class=\"c1\">\/\/ save the nodes in path<\/span>\r\n                <span class=\"nf\">dfs<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$u<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$path<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$matching<\/span><span class=\"p\">);<\/span>\r\n            <span class=\"p\">}<\/span>\r\n        <span class=\"p\">}<\/span>\r\n\r\n        <span class=\"k\">return<\/span> <span class=\"nb\">array_intersect_key<\/span><span class=\"p\">(<\/span><span class=\"nv\">$matching<\/span><span class=\"p\">,<\/span> <span class=\"nv\">$bigraph<\/span><span class=\"p\">);<\/span>\r\n    <span class=\"p\">}<\/span>\r\n\r\n    <span class=\"c1\">\/\/ left node idx is key<\/span>\r\n    <span class=\"c1\">\/\/ right nodes is value<\/span>\r\n    <span class=\"c1\">\/\/ eg. left nodes: 0 - 4, right nodes = 5 - 9<\/span>\r\n    <span class=\"nv\">$bigraph<\/span> <span class=\"o\">=<\/span> <span class=\"p\">[<\/span><span class=\"mi\">0<\/span> <span class=\"o\">=&gt;<\/span> <span class=\"p\">[<\/span><span class=\"mi\">6<\/span><span class=\"p\">,<\/span> <span class=\"mi\">9<\/span><span class=\"p\">],<\/span> <span class=\"mi\">1<\/span> <span class=\"o\">=&gt;<\/span> <span class=\"p\">[<\/span><span class=\"mi\">7<\/span><span class=\"p\">],<\/span> <span class=\"mi\">2<\/span> <span class=\"o\">=&gt;<\/span> <span class=\"p\">[<\/span><span class=\"mi\">6<\/span><span class=\"p\">,<\/span> <span class=\"mi\">8<\/span><span class=\"p\">],<\/span> <span class=\"mi\">3<\/span> <span class=\"o\">=&gt;<\/span> <span class=\"p\">[<\/span><span class=\"mi\">8<\/span><span class=\"p\">,<\/span> <span class=\"mi\">9<\/span><span class=\"p\">],<\/span> <span class=\"mi\">4<\/span> <span class=\"o\">=&gt;<\/span> <span class=\"p\">[<\/span><span class=\"mi\">5<\/span><span class=\"p\">,<\/span> <span class=\"mi\">7<\/span><span class=\"p\">]];<\/span>\r\n    <span class=\"nv\">$r<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">hungarian<\/span><span class=\"p\">(<\/span><span class=\"nv\">$bigraph<\/span><span class=\"p\">);<\/span>\r\n    <span class=\"nb\">print_r<\/span><span class=\"p\">(<\/span><span class=\"nv\">$r<\/span><span class=\"p\">);<\/span>\r\n<span class=\"cp\">?&gt;<\/span>\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\/\/ maximum matching algorithm \/\/ unweighted bipartite g [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[227],"class_list":["post-30907","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-227"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v21.5 (Yoast SEO v21.5) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>\u6700\u5927\u5339\u914d\uff08PHP\uff09 - Blog - Silicon Cloud<\/title>\n<meta name=\"description\" content=\"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.silicloud.com\/zh\/blog\/\u6700\u5927\u5339\u914d\uff08php\uff09\/\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u6700\u5927\u5339\u914d\uff08PHP\uff09\" \/>\n<meta property=\"og:description\" content=\"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.silicloud.com\/zh\/blog\/\u6700\u5927\u5339\u914d\uff08php\uff09\/\" \/>\n<meta property=\"og:site_name\" content=\"Blog - Silicon Cloud\" \/>\n<meta property=\"article:published_time\" content=\"2023-03-31T00:33:36+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-08-12T13:20:23+00:00\" \/>\n<meta name=\"author\" content=\"\u9038, \u79d1\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"\u9038, \u79d1\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/\",\"url\":\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/\",\"name\":\"\u6700\u5927\u5339\u914d\uff08PHP\uff09 - Blog - Silicon Cloud\",\"isPartOf\":{\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/#website\"},\"datePublished\":\"2023-03-31T00:33:36+00:00\",\"dateModified\":\"2025-08-12T13:20:23+00:00\",\"author\":{\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/85c1dae56e6ea1e695c73d33c684d487\"},\"description\":\"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0\",\"breadcrumb\":{\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.silicloud.com\/zh\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u6700\u5927\u5339\u914d\uff08PHP\uff09\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/#website\",\"url\":\"https:\/\/www.silicloud.com\/zh\/blog\/\",\"name\":\"Blog - Silicon Cloud\",\"description\":\"\",\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/85c1dae56e6ea1e695c73d33c684d487\",\"name\":\"\u9038, \u79d1\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/c94f6d9cbbfbca863fab309840bd690c153c95f8490c290ad2ed54dd693dad16?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/c94f6d9cbbfbca863fab309840bd690c153c95f8490c290ad2ed54dd693dad16?s=96&d=mm&r=g\",\"caption\":\"\u9038, \u79d1\"},\"url\":\"https:\/\/www.silicloud.com\/zh\/blog\/author\/keyi\/\"},{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#local-main-organization-logo\",\"url\":\"\",\"contentUrl\":\"\",\"caption\":\"Blog - Silicon Cloud\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"\u6700\u5927\u5339\u914d\uff08PHP\uff09 - Blog - Silicon Cloud","description":"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.silicloud.com\/zh\/blog\/\u6700\u5927\u5339\u914d\uff08php\uff09\/","og_locale":"zh_CN","og_type":"article","og_title":"\u6700\u5927\u5339\u914d\uff08PHP\uff09","og_description":"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0","og_url":"https:\/\/www.silicloud.com\/zh\/blog\/\u6700\u5927\u5339\u914d\uff08php\uff09\/","og_site_name":"Blog - Silicon Cloud","article_published_time":"2023-03-31T00:33:36+00:00","article_modified_time":"2025-08-12T13:20:23+00:00","author":"\u9038, \u79d1","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"\u9038, \u79d1"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/","url":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/","name":"\u6700\u5927\u5339\u914d\uff08PHP\uff09 - Blog - Silicon Cloud","isPartOf":{"@id":"https:\/\/www.silicloud.com\/zh\/blog\/#website"},"datePublished":"2023-03-31T00:33:36+00:00","dateModified":"2025-08-12T13:20:23+00:00","author":{"@id":"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/85c1dae56e6ea1e695c73d33c684d487"},"description":"\u5173\u4e8e\u6700\u5927\u5339\u914d\uff08PHP\uff09\u7684\u6280\u672f\u6587\u7ae0","breadcrumb":{"@id":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.silicloud.com\/zh\/blog\/"},{"@type":"ListItem","position":2,"name":"\u6700\u5927\u5339\u914d\uff08PHP\uff09"}]},{"@type":"WebSite","@id":"https:\/\/www.silicloud.com\/zh\/blog\/#website","url":"https:\/\/www.silicloud.com\/zh\/blog\/","name":"Blog - Silicon Cloud","description":"","inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/85c1dae56e6ea1e695c73d33c684d487","name":"\u9038, \u79d1","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.silicloud.com\/zh\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/c94f6d9cbbfbca863fab309840bd690c153c95f8490c290ad2ed54dd693dad16?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c94f6d9cbbfbca863fab309840bd690c153c95f8490c290ad2ed54dd693dad16?s=96&d=mm&r=g","caption":"\u9038, \u79d1"},"url":"https:\/\/www.silicloud.com\/zh\/blog\/author\/keyi\/"},{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.silicloud.com\/zh\/blog\/%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%88php%ef%bc%89\/#local-main-organization-logo","url":"","contentUrl":"","caption":"Blog - Silicon Cloud"}]}},"_links":{"self":[{"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/posts\/30907","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/comments?post=30907"}],"version-history":[{"count":1,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/posts\/30907\/revisions"}],"predecessor-version":[{"id":52490,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/posts\/30907\/revisions\/52490"}],"wp:attachment":[{"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/media?parent=30907"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/categories?post=30907"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.silicloud.com\/zh\/blog\/wp-json\/wp\/v2\/tags?post=30907"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}