很早之前就学过最近再温习一下，毕竟匈牙利算法虽然在解决二分图最大匹配问题上复杂度不如Dinic，但编程复杂度低很多，而且不容易写错。
其实如果对网络流有所涉猎，再来学习二分图最大匹配问题就太好理解了。此处默认读者已经了解了二分图最大匹配的问题模型及基本的网络流知识，若对网络流没有了解可以参见我的另一篇博客网络流的核心思想.
二分图问题可以很容易转化成网络流模型，即在原图中添加一源一汇，源点与左部各点相连，容量为 1 1 1，右部各点与汇点相连，容量为 1 1 1。由是我们只需跑一遍最大流即可求得二分图最大匹配。例如对于下面这幅图
#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .label text{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node rect,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node circle,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node ellipse,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node polygon,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node .label{text-align:center;fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node.clickable{cursor:pointer}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .arrowheadPath{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .flowchart-link{stroke:#333;fill:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edgeLabel rect{opacity:0.9}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edgeLabel span{color:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .cluster text{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .actor-line{stroke:grey}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sequenceNumber{fill:#fff}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #sequencenumber{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #crosshead path{fill:#333;stroke:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .messageText{fill:#333;stroke:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .labelText,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .loopText,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .noteText,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .section{stroke:none;opacity:0.2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .section2{fill:#fff400}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .section1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .section3{fill:#fff;opacity:0.2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sectionTitle0{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sectionTitle1{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sectionTitle2{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sectionTitle3{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .grid path{stroke-width:0}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task{stroke-width:2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText:not([font-size]){font-size:11px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task.clickable{cursor:pointer}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskText3{fill:#fff}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutside0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutside2{fill:#000}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutside1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .taskTextOutside3{fill:#000}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .active0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .active1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .active2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeText0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeText1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeText2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeText3{fill:#000 !important}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .done0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .done1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .done2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneText0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneText1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneText2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneText3{fill:#000 !important}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .crit0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .crit1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .crit2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCrit0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCrit1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCrit2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCrit0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCrit1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCrit2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .milestoneText{font-style:italic}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCritText0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCritText1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCritText2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .doneCritText3{fill:#000 !important}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCritText0,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCritText1,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCritText2,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .activeCritText3{fill:#000 !important}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.classGroup text .title{font-weight:bolder}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.clickable{cursor:pointer}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .dashed-line{stroke-dasharray:3}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .commit-id,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .commit-msg,#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edgeLabel text{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node circle.state-start{fill:black;stroke:black}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 #statediagram-barbEnd{fill:#9370db}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-state .divider{stroke:#9370db}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .note-edge{stroke-dasharray:5}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .error-icon{fill:#522}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .error-text{fill:#522;stroke:#522}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edge-thickness-normal{stroke-width:2px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .marker{fill:#333}#mermaid-svg-Zs4Y3a8Y5DJl9Wi3 .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-Zs4Y3a8Y5DJl9Wi3 { color: rgba(0, 0, 0, 0.75); font: normal normal normal normal 16px/26px -apple-system, "SF UI Text", Arial, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif; } 1 2 3 4 5 6mermaid终于画的像个二分图了
我们只需将其转化为这样的网络
#mermaid-svg-FOXD6z4uIzSli9JM .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-FOXD6z4uIzSli9JM .label text{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .node rect,#mermaid-svg-FOXD6z4uIzSli9JM .node circle,#mermaid-svg-FOXD6z4uIzSli9JM .node ellipse,#mermaid-svg-FOXD6z4uIzSli9JM .node polygon,#mermaid-svg-FOXD6z4uIzSli9JM .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-FOXD6z4uIzSli9JM .node .label{text-align:center;fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .node.clickable{cursor:pointer}#mermaid-svg-FOXD6z4uIzSli9JM .arrowheadPath{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-FOXD6z4uIzSli9JM .flowchart-link{stroke:#333;fill:none}#mermaid-svg-FOXD6z4uIzSli9JM .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-FOXD6z4uIzSli9JM .edgeLabel rect{opacity:0.9}#mermaid-svg-FOXD6z4uIzSli9JM .edgeLabel span{color:#333}#mermaid-svg-FOXD6z4uIzSli9JM .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-FOXD6z4uIzSli9JM .cluster text{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-FOXD6z4uIzSli9JM .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-FOXD6z4uIzSli9JM text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-FOXD6z4uIzSli9JM .actor-line{stroke:grey}#mermaid-svg-FOXD6z4uIzSli9JM .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-FOXD6z4uIzSli9JM .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-FOXD6z4uIzSli9JM #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-FOXD6z4uIzSli9JM .sequenceNumber{fill:#fff}#mermaid-svg-FOXD6z4uIzSli9JM #sequencenumber{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM #crosshead path{fill:#333;stroke:#333}#mermaid-svg-FOXD6z4uIzSli9JM .messageText{fill:#333;stroke:#333}#mermaid-svg-FOXD6z4uIzSli9JM .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-FOXD6z4uIzSli9JM .labelText,#mermaid-svg-FOXD6z4uIzSli9JM .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-FOXD6z4uIzSli9JM .loopText,#mermaid-svg-FOXD6z4uIzSli9JM .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-FOXD6z4uIzSli9JM .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-FOXD6z4uIzSli9JM .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-FOXD6z4uIzSli9JM .noteText,#mermaid-svg-FOXD6z4uIzSli9JM .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-FOXD6z4uIzSli9JM .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-FOXD6z4uIzSli9JM .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-FOXD6z4uIzSli9JM .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-FOXD6z4uIzSli9JM .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .section{stroke:none;opacity:0.2}#mermaid-svg-FOXD6z4uIzSli9JM .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-FOXD6z4uIzSli9JM .section2{fill:#fff400}#mermaid-svg-FOXD6z4uIzSli9JM .section1,#mermaid-svg-FOXD6z4uIzSli9JM .section3{fill:#fff;opacity:0.2}#mermaid-svg-FOXD6z4uIzSli9JM .sectionTitle0{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .sectionTitle1{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .sectionTitle2{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .sectionTitle3{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-FOXD6z4uIzSli9JM .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .grid path{stroke-width:0}#mermaid-svg-FOXD6z4uIzSli9JM .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-FOXD6z4uIzSli9JM .task{stroke-width:2}#mermaid-svg-FOXD6z4uIzSli9JM .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .taskText:not([font-size]){font-size:11px}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-FOXD6z4uIzSli9JM .task.clickable{cursor:pointer}#mermaid-svg-FOXD6z4uIzSli9JM .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-FOXD6z4uIzSli9JM .taskText0,#mermaid-svg-FOXD6z4uIzSli9JM .taskText1,#mermaid-svg-FOXD6z4uIzSli9JM .taskText2,#mermaid-svg-FOXD6z4uIzSli9JM .taskText3{fill:#fff}#mermaid-svg-FOXD6z4uIzSli9JM .task0,#mermaid-svg-FOXD6z4uIzSli9JM .task1,#mermaid-svg-FOXD6z4uIzSli9JM .task2,#mermaid-svg-FOXD6z4uIzSli9JM .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutside0,#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutside2{fill:#000}#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutside1,#mermaid-svg-FOXD6z4uIzSli9JM .taskTextOutside3{fill:#000}#mermaid-svg-FOXD6z4uIzSli9JM .active0,#mermaid-svg-FOXD6z4uIzSli9JM .active1,#mermaid-svg-FOXD6z4uIzSli9JM .active2,#mermaid-svg-FOXD6z4uIzSli9JM .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-FOXD6z4uIzSli9JM .activeText0,#mermaid-svg-FOXD6z4uIzSli9JM .activeText1,#mermaid-svg-FOXD6z4uIzSli9JM .activeText2,#mermaid-svg-FOXD6z4uIzSli9JM .activeText3{fill:#000 !important}#mermaid-svg-FOXD6z4uIzSli9JM .done0,#mermaid-svg-FOXD6z4uIzSli9JM .done1,#mermaid-svg-FOXD6z4uIzSli9JM .done2,#mermaid-svg-FOXD6z4uIzSli9JM .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-FOXD6z4uIzSli9JM .doneText0,#mermaid-svg-FOXD6z4uIzSli9JM .doneText1,#mermaid-svg-FOXD6z4uIzSli9JM .doneText2,#mermaid-svg-FOXD6z4uIzSli9JM .doneText3{fill:#000 !important}#mermaid-svg-FOXD6z4uIzSli9JM .crit0,#mermaid-svg-FOXD6z4uIzSli9JM .crit1,#mermaid-svg-FOXD6z4uIzSli9JM .crit2,#mermaid-svg-FOXD6z4uIzSli9JM .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-FOXD6z4uIzSli9JM .activeCrit0,#mermaid-svg-FOXD6z4uIzSli9JM .activeCrit1,#mermaid-svg-FOXD6z4uIzSli9JM .activeCrit2,#mermaid-svg-FOXD6z4uIzSli9JM .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-FOXD6z4uIzSli9JM .doneCrit0,#mermaid-svg-FOXD6z4uIzSli9JM .doneCrit1,#mermaid-svg-FOXD6z4uIzSli9JM .doneCrit2,#mermaid-svg-FOXD6z4uIzSli9JM .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-FOXD6z4uIzSli9JM .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-FOXD6z4uIzSli9JM .milestoneText{font-style:italic}#mermaid-svg-FOXD6z4uIzSli9JM .doneCritText0,#mermaid-svg-FOXD6z4uIzSli9JM .doneCritText1,#mermaid-svg-FOXD6z4uIzSli9JM .doneCritText2,#mermaid-svg-FOXD6z4uIzSli9JM .doneCritText3{fill:#000 !important}#mermaid-svg-FOXD6z4uIzSli9JM .activeCritText0,#mermaid-svg-FOXD6z4uIzSli9JM .activeCritText1,#mermaid-svg-FOXD6z4uIzSli9JM .activeCritText2,#mermaid-svg-FOXD6z4uIzSli9JM .activeCritText3{fill:#000 !important}#mermaid-svg-FOXD6z4uIzSli9JM .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-FOXD6z4uIzSli9JM g.classGroup text .title{font-weight:bolder}#mermaid-svg-FOXD6z4uIzSli9JM g.clickable{cursor:pointer}#mermaid-svg-FOXD6z4uIzSli9JM g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-FOXD6z4uIzSli9JM g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-FOXD6z4uIzSli9JM .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-FOXD6z4uIzSli9JM .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-FOXD6z4uIzSli9JM .dashed-line{stroke-dasharray:3}#mermaid-svg-FOXD6z4uIzSli9JM #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM .commit-id,#mermaid-svg-FOXD6z4uIzSli9JM .commit-msg,#mermaid-svg-FOXD6z4uIzSli9JM .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-FOXD6z4uIzSli9JM g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-FOXD6z4uIzSli9JM g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-FOXD6z4uIzSli9JM g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-FOXD6z4uIzSli9JM .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-FOXD6z4uIzSli9JM .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-FOXD6z4uIzSli9JM .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-FOXD6z4uIzSli9JM .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-FOXD6z4uIzSli9JM .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-FOXD6z4uIzSli9JM .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-FOXD6z4uIzSli9JM .edgeLabel text{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-FOXD6z4uIzSli9JM .node circle.state-start{fill:black;stroke:black}#mermaid-svg-FOXD6z4uIzSli9JM .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-FOXD6z4uIzSli9JM #statediagram-barbEnd{fill:#9370db}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-state .divider{stroke:#9370db}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-FOXD6z4uIzSli9JM .note-edge{stroke-dasharray:5}#mermaid-svg-FOXD6z4uIzSli9JM .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-FOXD6z4uIzSli9JM .error-icon{fill:#522}#mermaid-svg-FOXD6z4uIzSli9JM .error-text{fill:#522;stroke:#522}#mermaid-svg-FOXD6z4uIzSli9JM .edge-thickness-normal{stroke-width:2px}#mermaid-svg-FOXD6z4uIzSli9JM .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-FOXD6z4uIzSli9JM .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-FOXD6z4uIzSli9JM .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-FOXD6z4uIzSli9JM .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-FOXD6z4uIzSli9JM .marker{fill:#333}#mermaid-svg-FOXD6z4uIzSli9JM .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-FOXD6z4uIzSli9JM { color: rgba(0, 0, 0, 0.75); font: normal normal normal normal 16px/26px -apple-system, "SF UI Text", Arial, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif; } 1 1 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7即可在网络上跑最大流求解。而我们经常用到的网络流算法如Dinic其实是基于Ford-Fulkerson的思想即增广路的思想，我们很容易联想，在二分图这样的特殊图上，是否有更简易的找增广路的办法呢？显然是有的，而且特别暴力。我们重新考虑一个的二分图。我们依次考虑左部的点，然后遍历它的邻点，然后寻找一个可匹配点，然后
#mermaid-svg-WntV0dOtb1bUovON .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-WntV0dOtb1bUovON .label text{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .node rect,#mermaid-svg-WntV0dOtb1bUovON .node circle,#mermaid-svg-WntV0dOtb1bUovON .node ellipse,#mermaid-svg-WntV0dOtb1bUovON .node polygon,#mermaid-svg-WntV0dOtb1bUovON .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-WntV0dOtb1bUovON .node .label{text-align:center;fill:#333}#mermaid-svg-WntV0dOtb1bUovON .node.clickable{cursor:pointer}#mermaid-svg-WntV0dOtb1bUovON .arrowheadPath{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-WntV0dOtb1bUovON .flowchart-link{stroke:#333;fill:none}#mermaid-svg-WntV0dOtb1bUovON .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-WntV0dOtb1bUovON .edgeLabel rect{opacity:0.9}#mermaid-svg-WntV0dOtb1bUovON .edgeLabel span{color:#333}#mermaid-svg-WntV0dOtb1bUovON .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-WntV0dOtb1bUovON .cluster text{fill:#333}#mermaid-svg-WntV0dOtb1bUovON div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-WntV0dOtb1bUovON .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-WntV0dOtb1bUovON text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-WntV0dOtb1bUovON .actor-line{stroke:grey}#mermaid-svg-WntV0dOtb1bUovON .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-WntV0dOtb1bUovON .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-WntV0dOtb1bUovON #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-WntV0dOtb1bUovON .sequenceNumber{fill:#fff}#mermaid-svg-WntV0dOtb1bUovON #sequencenumber{fill:#333}#mermaid-svg-WntV0dOtb1bUovON #crosshead path{fill:#333;stroke:#333}#mermaid-svg-WntV0dOtb1bUovON .messageText{fill:#333;stroke:#333}#mermaid-svg-WntV0dOtb1bUovON .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-WntV0dOtb1bUovON .labelText,#mermaid-svg-WntV0dOtb1bUovON .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-WntV0dOtb1bUovON .loopText,#mermaid-svg-WntV0dOtb1bUovON .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-WntV0dOtb1bUovON .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-WntV0dOtb1bUovON .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-WntV0dOtb1bUovON .noteText,#mermaid-svg-WntV0dOtb1bUovON .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-WntV0dOtb1bUovON .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-WntV0dOtb1bUovON .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-WntV0dOtb1bUovON .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-WntV0dOtb1bUovON .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .section{stroke:none;opacity:0.2}#mermaid-svg-WntV0dOtb1bUovON .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-WntV0dOtb1bUovON .section2{fill:#fff400}#mermaid-svg-WntV0dOtb1bUovON .section1,#mermaid-svg-WntV0dOtb1bUovON .section3{fill:#fff;opacity:0.2}#mermaid-svg-WntV0dOtb1bUovON .sectionTitle0{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .sectionTitle1{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .sectionTitle2{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .sectionTitle3{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-WntV0dOtb1bUovON .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .grid path{stroke-width:0}#mermaid-svg-WntV0dOtb1bUovON .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-WntV0dOtb1bUovON .task{stroke-width:2}#mermaid-svg-WntV0dOtb1bUovON .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .taskText:not([font-size]){font-size:11px}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-WntV0dOtb1bUovON .task.clickable{cursor:pointer}#mermaid-svg-WntV0dOtb1bUovON .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-WntV0dOtb1bUovON .taskText0,#mermaid-svg-WntV0dOtb1bUovON .taskText1,#mermaid-svg-WntV0dOtb1bUovON .taskText2,#mermaid-svg-WntV0dOtb1bUovON .taskText3{fill:#fff}#mermaid-svg-WntV0dOtb1bUovON .task0,#mermaid-svg-WntV0dOtb1bUovON .task1,#mermaid-svg-WntV0dOtb1bUovON .task2,#mermaid-svg-WntV0dOtb1bUovON .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutside0,#mermaid-svg-WntV0dOtb1bUovON .taskTextOutside2{fill:#000}#mermaid-svg-WntV0dOtb1bUovON .taskTextOutside1,#mermaid-svg-WntV0dOtb1bUovON .taskTextOutside3{fill:#000}#mermaid-svg-WntV0dOtb1bUovON .active0,#mermaid-svg-WntV0dOtb1bUovON .active1,#mermaid-svg-WntV0dOtb1bUovON .active2,#mermaid-svg-WntV0dOtb1bUovON .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-WntV0dOtb1bUovON .activeText0,#mermaid-svg-WntV0dOtb1bUovON .activeText1,#mermaid-svg-WntV0dOtb1bUovON .activeText2,#mermaid-svg-WntV0dOtb1bUovON .activeText3{fill:#000 !important}#mermaid-svg-WntV0dOtb1bUovON .done0,#mermaid-svg-WntV0dOtb1bUovON .done1,#mermaid-svg-WntV0dOtb1bUovON .done2,#mermaid-svg-WntV0dOtb1bUovON .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-WntV0dOtb1bUovON .doneText0,#mermaid-svg-WntV0dOtb1bUovON .doneText1,#mermaid-svg-WntV0dOtb1bUovON .doneText2,#mermaid-svg-WntV0dOtb1bUovON .doneText3{fill:#000 !important}#mermaid-svg-WntV0dOtb1bUovON .crit0,#mermaid-svg-WntV0dOtb1bUovON .crit1,#mermaid-svg-WntV0dOtb1bUovON .crit2,#mermaid-svg-WntV0dOtb1bUovON .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-WntV0dOtb1bUovON .activeCrit0,#mermaid-svg-WntV0dOtb1bUovON .activeCrit1,#mermaid-svg-WntV0dOtb1bUovON .activeCrit2,#mermaid-svg-WntV0dOtb1bUovON .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-WntV0dOtb1bUovON .doneCrit0,#mermaid-svg-WntV0dOtb1bUovON .doneCrit1,#mermaid-svg-WntV0dOtb1bUovON .doneCrit2,#mermaid-svg-WntV0dOtb1bUovON .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-WntV0dOtb1bUovON .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-WntV0dOtb1bUovON .milestoneText{font-style:italic}#mermaid-svg-WntV0dOtb1bUovON .doneCritText0,#mermaid-svg-WntV0dOtb1bUovON .doneCritText1,#mermaid-svg-WntV0dOtb1bUovON .doneCritText2,#mermaid-svg-WntV0dOtb1bUovON .doneCritText3{fill:#000 !important}#mermaid-svg-WntV0dOtb1bUovON .activeCritText0,#mermaid-svg-WntV0dOtb1bUovON .activeCritText1,#mermaid-svg-WntV0dOtb1bUovON .activeCritText2,#mermaid-svg-WntV0dOtb1bUovON .activeCritText3{fill:#000 !important}#mermaid-svg-WntV0dOtb1bUovON .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-WntV0dOtb1bUovON g.classGroup text .title{font-weight:bolder}#mermaid-svg-WntV0dOtb1bUovON g.clickable{cursor:pointer}#mermaid-svg-WntV0dOtb1bUovON g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-WntV0dOtb1bUovON g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-WntV0dOtb1bUovON .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-WntV0dOtb1bUovON .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-WntV0dOtb1bUovON .dashed-line{stroke-dasharray:3}#mermaid-svg-WntV0dOtb1bUovON #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON .commit-id,#mermaid-svg-WntV0dOtb1bUovON .commit-msg,#mermaid-svg-WntV0dOtb1bUovON .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-WntV0dOtb1bUovON g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-WntV0dOtb1bUovON g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-WntV0dOtb1bUovON g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-WntV0dOtb1bUovON g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-WntV0dOtb1bUovON .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-WntV0dOtb1bUovON .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-WntV0dOtb1bUovON .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-WntV0dOtb1bUovON .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-WntV0dOtb1bUovON .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-WntV0dOtb1bUovON .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-WntV0dOtb1bUovON .edgeLabel text{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-WntV0dOtb1bUovON .node circle.state-start{fill:black;stroke:black}#mermaid-svg-WntV0dOtb1bUovON .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-WntV0dOtb1bUovON #statediagram-barbEnd{fill:#9370db}#mermaid-svg-WntV0dOtb1bUovON .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-WntV0dOtb1bUovON .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-WntV0dOtb1bUovON .statediagram-state .divider{stroke:#9370db}#mermaid-svg-WntV0dOtb1bUovON .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-WntV0dOtb1bUovON .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-WntV0dOtb1bUovON .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-WntV0dOtb1bUovON .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-WntV0dOtb1bUovON .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-WntV0dOtb1bUovON .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-WntV0dOtb1bUovON .note-edge{stroke-dasharray:5}#mermaid-svg-WntV0dOtb1bUovON .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-WntV0dOtb1bUovON .error-icon{fill:#522}#mermaid-svg-WntV0dOtb1bUovON .error-text{fill:#522;stroke:#522}#mermaid-svg-WntV0dOtb1bUovON .edge-thickness-normal{stroke-width:2px}#mermaid-svg-WntV0dOtb1bUovON .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-WntV0dOtb1bUovON .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-WntV0dOtb1bUovON .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-WntV0dOtb1bUovON .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-WntV0dOtb1bUovON .marker{fill:#333}#mermaid-svg-WntV0dOtb1bUovON .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-WntV0dOtb1bUovON { color: rgba(0, 0, 0, 0.75); font: normal normal normal normal 16px/26px -apple-system, "SF UI Text", Arial, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif; } 1 2 3 4 5这里mermaid把1画到下面了，但我们还是以编号顺序而不是视觉顺序来考虑
首先考虑左部的 1 1 1，我们考虑它的邻点，发现 4 4 4未匹配，直接产生匹配。
#mermaid-svg-39SixYV6I51Amy1W .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-39SixYV6I51Amy1W .label text{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .node rect,#mermaid-svg-39SixYV6I51Amy1W .node circle,#mermaid-svg-39SixYV6I51Amy1W .node ellipse,#mermaid-svg-39SixYV6I51Amy1W .node polygon,#mermaid-svg-39SixYV6I51Amy1W .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-39SixYV6I51Amy1W .node .label{text-align:center;fill:#333}#mermaid-svg-39SixYV6I51Amy1W .node.clickable{cursor:pointer}#mermaid-svg-39SixYV6I51Amy1W .arrowheadPath{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-39SixYV6I51Amy1W .flowchart-link{stroke:#333;fill:none}#mermaid-svg-39SixYV6I51Amy1W .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-39SixYV6I51Amy1W .edgeLabel rect{opacity:0.9}#mermaid-svg-39SixYV6I51Amy1W .edgeLabel span{color:#333}#mermaid-svg-39SixYV6I51Amy1W .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-39SixYV6I51Amy1W .cluster text{fill:#333}#mermaid-svg-39SixYV6I51Amy1W div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-39SixYV6I51Amy1W .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-39SixYV6I51Amy1W text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-39SixYV6I51Amy1W .actor-line{stroke:grey}#mermaid-svg-39SixYV6I51Amy1W .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-39SixYV6I51Amy1W .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-39SixYV6I51Amy1W #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-39SixYV6I51Amy1W .sequenceNumber{fill:#fff}#mermaid-svg-39SixYV6I51Amy1W #sequencenumber{fill:#333}#mermaid-svg-39SixYV6I51Amy1W #crosshead path{fill:#333;stroke:#333}#mermaid-svg-39SixYV6I51Amy1W .messageText{fill:#333;stroke:#333}#mermaid-svg-39SixYV6I51Amy1W .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-39SixYV6I51Amy1W .labelText,#mermaid-svg-39SixYV6I51Amy1W .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-39SixYV6I51Amy1W .loopText,#mermaid-svg-39SixYV6I51Amy1W .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-39SixYV6I51Amy1W .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-39SixYV6I51Amy1W .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-39SixYV6I51Amy1W .noteText,#mermaid-svg-39SixYV6I51Amy1W .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-39SixYV6I51Amy1W .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-39SixYV6I51Amy1W .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-39SixYV6I51Amy1W .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-39SixYV6I51Amy1W .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .section{stroke:none;opacity:0.2}#mermaid-svg-39SixYV6I51Amy1W .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-39SixYV6I51Amy1W .section2{fill:#fff400}#mermaid-svg-39SixYV6I51Amy1W .section1,#mermaid-svg-39SixYV6I51Amy1W .section3{fill:#fff;opacity:0.2}#mermaid-svg-39SixYV6I51Amy1W .sectionTitle0{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .sectionTitle1{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .sectionTitle2{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .sectionTitle3{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-39SixYV6I51Amy1W .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .grid path{stroke-width:0}#mermaid-svg-39SixYV6I51Amy1W .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-39SixYV6I51Amy1W .task{stroke-width:2}#mermaid-svg-39SixYV6I51Amy1W .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .taskText:not([font-size]){font-size:11px}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-39SixYV6I51Amy1W .task.clickable{cursor:pointer}#mermaid-svg-39SixYV6I51Amy1W .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-39SixYV6I51Amy1W .taskText0,#mermaid-svg-39SixYV6I51Amy1W .taskText1,#mermaid-svg-39SixYV6I51Amy1W .taskText2,#mermaid-svg-39SixYV6I51Amy1W .taskText3{fill:#fff}#mermaid-svg-39SixYV6I51Amy1W .task0,#mermaid-svg-39SixYV6I51Amy1W .task1,#mermaid-svg-39SixYV6I51Amy1W .task2,#mermaid-svg-39SixYV6I51Amy1W .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutside0,#mermaid-svg-39SixYV6I51Amy1W .taskTextOutside2{fill:#000}#mermaid-svg-39SixYV6I51Amy1W .taskTextOutside1,#mermaid-svg-39SixYV6I51Amy1W .taskTextOutside3{fill:#000}#mermaid-svg-39SixYV6I51Amy1W .active0,#mermaid-svg-39SixYV6I51Amy1W .active1,#mermaid-svg-39SixYV6I51Amy1W .active2,#mermaid-svg-39SixYV6I51Amy1W .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-39SixYV6I51Amy1W .activeText0,#mermaid-svg-39SixYV6I51Amy1W .activeText1,#mermaid-svg-39SixYV6I51Amy1W .activeText2,#mermaid-svg-39SixYV6I51Amy1W .activeText3{fill:#000 !important}#mermaid-svg-39SixYV6I51Amy1W .done0,#mermaid-svg-39SixYV6I51Amy1W .done1,#mermaid-svg-39SixYV6I51Amy1W .done2,#mermaid-svg-39SixYV6I51Amy1W .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-39SixYV6I51Amy1W .doneText0,#mermaid-svg-39SixYV6I51Amy1W .doneText1,#mermaid-svg-39SixYV6I51Amy1W .doneText2,#mermaid-svg-39SixYV6I51Amy1W .doneText3{fill:#000 !important}#mermaid-svg-39SixYV6I51Amy1W .crit0,#mermaid-svg-39SixYV6I51Amy1W .crit1,#mermaid-svg-39SixYV6I51Amy1W .crit2,#mermaid-svg-39SixYV6I51Amy1W .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-39SixYV6I51Amy1W .activeCrit0,#mermaid-svg-39SixYV6I51Amy1W .activeCrit1,#mermaid-svg-39SixYV6I51Amy1W .activeCrit2,#mermaid-svg-39SixYV6I51Amy1W .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-39SixYV6I51Amy1W .doneCrit0,#mermaid-svg-39SixYV6I51Amy1W .doneCrit1,#mermaid-svg-39SixYV6I51Amy1W .doneCrit2,#mermaid-svg-39SixYV6I51Amy1W .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-39SixYV6I51Amy1W .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-39SixYV6I51Amy1W .milestoneText{font-style:italic}#mermaid-svg-39SixYV6I51Amy1W .doneCritText0,#mermaid-svg-39SixYV6I51Amy1W .doneCritText1,#mermaid-svg-39SixYV6I51Amy1W .doneCritText2,#mermaid-svg-39SixYV6I51Amy1W .doneCritText3{fill:#000 !important}#mermaid-svg-39SixYV6I51Amy1W .activeCritText0,#mermaid-svg-39SixYV6I51Amy1W .activeCritText1,#mermaid-svg-39SixYV6I51Amy1W .activeCritText2,#mermaid-svg-39SixYV6I51Amy1W .activeCritText3{fill:#000 !important}#mermaid-svg-39SixYV6I51Amy1W .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-39SixYV6I51Amy1W g.classGroup text .title{font-weight:bolder}#mermaid-svg-39SixYV6I51Amy1W g.clickable{cursor:pointer}#mermaid-svg-39SixYV6I51Amy1W g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-39SixYV6I51Amy1W g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-39SixYV6I51Amy1W .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-39SixYV6I51Amy1W .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-39SixYV6I51Amy1W .dashed-line{stroke-dasharray:3}#mermaid-svg-39SixYV6I51Amy1W #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W .commit-id,#mermaid-svg-39SixYV6I51Amy1W .commit-msg,#mermaid-svg-39SixYV6I51Amy1W .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-39SixYV6I51Amy1W g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-39SixYV6I51Amy1W g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-39SixYV6I51Amy1W g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-39SixYV6I51Amy1W g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-39SixYV6I51Amy1W .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-39SixYV6I51Amy1W .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-39SixYV6I51Amy1W .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-39SixYV6I51Amy1W .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-39SixYV6I51Amy1W .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-39SixYV6I51Amy1W .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-39SixYV6I51Amy1W .edgeLabel text{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-39SixYV6I51Amy1W .node circle.state-start{fill:black;stroke:black}#mermaid-svg-39SixYV6I51Amy1W .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-39SixYV6I51Amy1W #statediagram-barbEnd{fill:#9370db}#mermaid-svg-39SixYV6I51Amy1W .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-39SixYV6I51Amy1W .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-39SixYV6I51Amy1W .statediagram-state .divider{stroke:#9370db}#mermaid-svg-39SixYV6I51Amy1W .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-39SixYV6I51Amy1W .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-39SixYV6I51Amy1W .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-39SixYV6I51Amy1W .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-39SixYV6I51Amy1W .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-39SixYV6I51Amy1W .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-39SixYV6I51Amy1W .note-edge{stroke-dasharray:5}#mermaid-svg-39SixYV6I51Amy1W .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-39SixYV6I51Amy1W .error-icon{fill:#522}#mermaid-svg-39SixYV6I51Amy1W .error-text{fill:#522;stroke:#522}#mermaid-svg-39SixYV6I51Amy1W .edge-thickness-normal{stroke-width:2px}#mermaid-svg-39SixYV6I51Amy1W .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-39SixYV6I51Amy1W .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-39SixYV6I51Amy1W .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-39SixYV6I51Amy1W .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-39SixYV6I51Amy1W .marker{fill:#333}#mermaid-svg-39SixYV6I51Amy1W .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-39SixYV6I51Amy1W { color: rgba(0, 0, 0, 0.75); font: normal normal normal normal 16px/26px -apple-system, "SF UI Text", Arial, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif; } 1 2 3 4 5一个点有且只能产生一对匹配，故当匹配生成后，我们直接考虑左部下一个点 2 2 2。
2 2 2只与右部的 4 4 4有边相连，但此时 4 4 4已产生匹配， 2 2 2并不能与 4 4 4产生匹配，怎么处理这种情况？如果选择跳过 2 2 2，那么对于后面的 3 3 3也是一样跳过的情况，最终产生的匹配只有 1 1 1对，显然有问题。联想一下之前介绍的网络流模型解决的方法，其实这里我们就是要找增广。
寻找增广路其实有一个很简单暴力的方法，就是看当前已匹配的右部的点对应的左部的点的邻点是否还有能匹配的点，如果有那么就让这个左部的点跟新的点匹配，为当前点腾出空间（显然这是一个递归的过程）。
我们具体情况分析一下，现在考虑左部的点 2 2 2，其唯一相连的右部的点 4 4 4已与左部的 1 1 1匹配。按照上面的说法，我们仅需为 1 1 1找一个新的匹配点。我们遍历 1 1 1的所有邻点， 4 4 4被访问了，所以我们找到右部的 5 5 5，发现 5 5 5尚未匹配，我们可以让 1 1 1匹配 5 5 5，再让 2 2 2匹配之前的 4 4 4，以达到增广目的。
#mermaid-svg-85WrTcJ42NkzE0P2 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .label text{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .node rect,#mermaid-svg-85WrTcJ42NkzE0P2 .node circle,#mermaid-svg-85WrTcJ42NkzE0P2 .node ellipse,#mermaid-svg-85WrTcJ42NkzE0P2 .node polygon,#mermaid-svg-85WrTcJ42NkzE0P2 .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-85WrTcJ42NkzE0P2 .node .label{text-align:center;fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .node.clickable{cursor:pointer}#mermaid-svg-85WrTcJ42NkzE0P2 .arrowheadPath{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-85WrTcJ42NkzE0P2 .flowchart-link{stroke:#333;fill:none}#mermaid-svg-85WrTcJ42NkzE0P2 .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-85WrTcJ42NkzE0P2 .edgeLabel rect{opacity:0.9}#mermaid-svg-85WrTcJ42NkzE0P2 .edgeLabel span{color:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-85WrTcJ42NkzE0P2 .cluster text{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-85WrTcJ42NkzE0P2 .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-85WrTcJ42NkzE0P2 text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-85WrTcJ42NkzE0P2 .actor-line{stroke:grey}#mermaid-svg-85WrTcJ42NkzE0P2 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-85WrTcJ42NkzE0P2 #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .sequenceNumber{fill:#fff}#mermaid-svg-85WrTcJ42NkzE0P2 #sequencenumber{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 #crosshead path{fill:#333;stroke:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .messageText{fill:#333;stroke:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-85WrTcJ42NkzE0P2 .labelText,#mermaid-svg-85WrTcJ42NkzE0P2 .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-85WrTcJ42NkzE0P2 .loopText,#mermaid-svg-85WrTcJ42NkzE0P2 .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-85WrTcJ42NkzE0P2 .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-85WrTcJ42NkzE0P2 .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-85WrTcJ42NkzE0P2 .noteText,#mermaid-svg-85WrTcJ42NkzE0P2 .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-85WrTcJ42NkzE0P2 .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-85WrTcJ42NkzE0P2 .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-85WrTcJ42NkzE0P2 .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-85WrTcJ42NkzE0P2 .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .section{stroke:none;opacity:0.2}#mermaid-svg-85WrTcJ42NkzE0P2 .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-85WrTcJ42NkzE0P2 .section2{fill:#fff400}#mermaid-svg-85WrTcJ42NkzE0P2 .section1,#mermaid-svg-85WrTcJ42NkzE0P2 .section3{fill:#fff;opacity:0.2}#mermaid-svg-85WrTcJ42NkzE0P2 .sectionTitle0{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .sectionTitle1{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .sectionTitle2{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .sectionTitle3{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-85WrTcJ42NkzE0P2 .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .grid path{stroke-width:0}#mermaid-svg-85WrTcJ42NkzE0P2 .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-85WrTcJ42NkzE0P2 .task{stroke-width:2}#mermaid-svg-85WrTcJ42NkzE0P2 .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .taskText:not([font-size]){font-size:11px}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-85WrTcJ42NkzE0P2 .task.clickable{cursor:pointer}#mermaid-svg-85WrTcJ42NkzE0P2 .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-85WrTcJ42NkzE0P2 .taskText0,#mermaid-svg-85WrTcJ42NkzE0P2 .taskText1,#mermaid-svg-85WrTcJ42NkzE0P2 .taskText2,#mermaid-svg-85WrTcJ42NkzE0P2 .taskText3{fill:#fff}#mermaid-svg-85WrTcJ42NkzE0P2 .task0,#mermaid-svg-85WrTcJ42NkzE0P2 .task1,#mermaid-svg-85WrTcJ42NkzE0P2 .task2,#mermaid-svg-85WrTcJ42NkzE0P2 .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutside0,#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutside2{fill:#000}#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutside1,#mermaid-svg-85WrTcJ42NkzE0P2 .taskTextOutside3{fill:#000}#mermaid-svg-85WrTcJ42NkzE0P2 .active0,#mermaid-svg-85WrTcJ42NkzE0P2 .active1,#mermaid-svg-85WrTcJ42NkzE0P2 .active2,#mermaid-svg-85WrTcJ42NkzE0P2 .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-85WrTcJ42NkzE0P2 .activeText0,#mermaid-svg-85WrTcJ42NkzE0P2 .activeText1,#mermaid-svg-85WrTcJ42NkzE0P2 .activeText2,#mermaid-svg-85WrTcJ42NkzE0P2 .activeText3{fill:#000 !important}#mermaid-svg-85WrTcJ42NkzE0P2 .done0,#mermaid-svg-85WrTcJ42NkzE0P2 .done1,#mermaid-svg-85WrTcJ42NkzE0P2 .done2,#mermaid-svg-85WrTcJ42NkzE0P2 .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-85WrTcJ42NkzE0P2 .doneText0,#mermaid-svg-85WrTcJ42NkzE0P2 .doneText1,#mermaid-svg-85WrTcJ42NkzE0P2 .doneText2,#mermaid-svg-85WrTcJ42NkzE0P2 .doneText3{fill:#000 !important}#mermaid-svg-85WrTcJ42NkzE0P2 .crit0,#mermaid-svg-85WrTcJ42NkzE0P2 .crit1,#mermaid-svg-85WrTcJ42NkzE0P2 .crit2,#mermaid-svg-85WrTcJ42NkzE0P2 .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-85WrTcJ42NkzE0P2 .activeCrit0,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCrit1,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCrit2,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-85WrTcJ42NkzE0P2 .doneCrit0,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCrit1,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCrit2,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-85WrTcJ42NkzE0P2 .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-85WrTcJ42NkzE0P2 .milestoneText{font-style:italic}#mermaid-svg-85WrTcJ42NkzE0P2 .doneCritText0,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCritText1,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCritText2,#mermaid-svg-85WrTcJ42NkzE0P2 .doneCritText3{fill:#000 !important}#mermaid-svg-85WrTcJ42NkzE0P2 .activeCritText0,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCritText1,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCritText2,#mermaid-svg-85WrTcJ42NkzE0P2 .activeCritText3{fill:#000 !important}#mermaid-svg-85WrTcJ42NkzE0P2 .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-85WrTcJ42NkzE0P2 g.classGroup text .title{font-weight:bolder}#mermaid-svg-85WrTcJ42NkzE0P2 g.clickable{cursor:pointer}#mermaid-svg-85WrTcJ42NkzE0P2 g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-85WrTcJ42NkzE0P2 g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-85WrTcJ42NkzE0P2 .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-85WrTcJ42NkzE0P2 .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-85WrTcJ42NkzE0P2 .dashed-line{stroke-dasharray:3}#mermaid-svg-85WrTcJ42NkzE0P2 #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 .commit-id,#mermaid-svg-85WrTcJ42NkzE0P2 .commit-msg,#mermaid-svg-85WrTcJ42NkzE0P2 .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-85WrTcJ42NkzE0P2 g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-85WrTcJ42NkzE0P2 g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-85WrTcJ42NkzE0P2 g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-85WrTcJ42NkzE0P2 .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-85WrTcJ42NkzE0P2 .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-85WrTcJ42NkzE0P2 .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-85WrTcJ42NkzE0P2 .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-85WrTcJ42NkzE0P2 .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-85WrTcJ42NkzE0P2 .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-85WrTcJ42NkzE0P2 .edgeLabel text{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-85WrTcJ42NkzE0P2 .node circle.state-start{fill:black;stroke:black}#mermaid-svg-85WrTcJ42NkzE0P2 .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-85WrTcJ42NkzE0P2 #statediagram-barbEnd{fill:#9370db}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-state .divider{stroke:#9370db}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-85WrTcJ42NkzE0P2 .note-edge{stroke-dasharray:5}#mermaid-svg-85WrTcJ42NkzE0P2 .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-85WrTcJ42NkzE0P2 .error-icon{fill:#522}#mermaid-svg-85WrTcJ42NkzE0P2 .error-text{fill:#522;stroke:#522}#mermaid-svg-85WrTcJ42NkzE0P2 .edge-thickness-normal{stroke-width:2px}#mermaid-svg-85WrTcJ42NkzE0P2 .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-85WrTcJ42NkzE0P2 .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-85WrTcJ42NkzE0P2 .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-85WrTcJ42NkzE0P2 .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-85WrTcJ42NkzE0P2 .marker{fill:#333}#mermaid-svg-85WrTcJ42NkzE0P2 .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-85WrTcJ42NkzE0P2 { color: rgba(0, 0, 0, 0.75); font: normal normal normal normal 16px/26px -apple-system, "SF UI Text", Arial, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif; } 1 2 3 4 5可以自行在更复杂的图上手动尝试这一操作加深理解。显然，每对一个左部的点做上述操作，至多只会增加 1 1 1对匹配。而这一做法其实是基于一种贪心的思想，即每次操作答案都只会增不会减。
// // Created by Visors on 2020/10/7. // // 题目名：P3386 【模板】二分图最大匹配 // 题目来源：luogu // 题目链接：https://www.luogu.com.cn/problem/P3386 // 算法：匈牙利算法 // 用途：二分图最大匹配 // 时间复杂度：O(nm) // #include <bits/stdc++.h> using namespace std; int n, m, vertexNum, edgeNum; struct Edge { int to; // 边终点 int next; // 前向弧 Edge() = default; Edge(int to, int next) : to(to), next(next) {} }; vector<Edge> edges; // 边集 vector<int> heads; // 首边集 vector<bool> vis; // 点访问标记 vector<int> match; // 点匹配记录 inline void addEdge(int u, int v) { edges.emplace_back(v, heads[u]); heads[u] = edges.size() - 1; edges.emplace_back(u, heads[v]); heads[v] = edges.size() - 1; } bool dfs(int u) { for (int i = heads[u], v; ~i; i = edges[i].next) { if (!vis[v = edges[i].to]) { vis[v] = true; // 如果未匹配，则直接产生新匹配达到增广 // 如果已匹配，尝试DFS找增广路，若找到，则回溯更新新的匹配 if (!match[v] || dfs(match[v])) { // cout << "augment " << v << " from " << match[v] << " to: " << u << endl; match[v] = u; return true; } } } return false; } inline int hungary() { int max_match = 0; for (int i = 1; i <= n; i++) { fill(vis.begin(), vis.end(), false); vis[i] = true; if (dfs(i)) max_match++; } return max_match; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m >> edgeNum; vertexNum = n + m; heads.resize(vertexNum + 1, -1); vis.resize(vertexNum + 1); match.resize(vertexNum + 1); for (int i = 1, u, v; i <= edgeNum; i++) { cin >> u >> v; addEdge(u, v + n); } cout << hungary() << endl; return 0; }