最小路径覆盖转二分图模型

最小路径覆盖

所谓DAG的路径覆盖，即在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联。

#mermaid-svg-8vopoyGDkRf90ox0 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-8vopoyGDkRf90ox0 .label text{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .node rect,#mermaid-svg-8vopoyGDkRf90ox0 .node circle,#mermaid-svg-8vopoyGDkRf90ox0 .node ellipse,#mermaid-svg-8vopoyGDkRf90ox0 .node polygon,#mermaid-svg-8vopoyGDkRf90ox0 .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-8vopoyGDkRf90ox0 .node .label{text-align:center;fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .node.clickable{cursor:pointer}#mermaid-svg-8vopoyGDkRf90ox0 .arrowheadPath{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-8vopoyGDkRf90ox0 .flowchart-link{stroke:#333;fill:none}#mermaid-svg-8vopoyGDkRf90ox0 .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-8vopoyGDkRf90ox0 .edgeLabel rect{opacity:0.9}#mermaid-svg-8vopoyGDkRf90ox0 .edgeLabel span{color:#333}#mermaid-svg-8vopoyGDkRf90ox0 .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-8vopoyGDkRf90ox0 .cluster text{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 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-8vopoyGDkRf90ox0 .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-8vopoyGDkRf90ox0 text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-8vopoyGDkRf90ox0 .actor-line{stroke:grey}#mermaid-svg-8vopoyGDkRf90ox0 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-8vopoyGDkRf90ox0 .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-8vopoyGDkRf90ox0 #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-8vopoyGDkRf90ox0 .sequenceNumber{fill:#fff}#mermaid-svg-8vopoyGDkRf90ox0 #sequencenumber{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 #crosshead path{fill:#333;stroke:#333}#mermaid-svg-8vopoyGDkRf90ox0 .messageText{fill:#333;stroke:#333}#mermaid-svg-8vopoyGDkRf90ox0 .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-8vopoyGDkRf90ox0 .labelText,#mermaid-svg-8vopoyGDkRf90ox0 .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-8vopoyGDkRf90ox0 .loopText,#mermaid-svg-8vopoyGDkRf90ox0 .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-8vopoyGDkRf90ox0 .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-8vopoyGDkRf90ox0 .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-8vopoyGDkRf90ox0 .noteText,#mermaid-svg-8vopoyGDkRf90ox0 .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-8vopoyGDkRf90ox0 .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-8vopoyGDkRf90ox0 .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-8vopoyGDkRf90ox0 .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-8vopoyGDkRf90ox0 .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .section{stroke:none;opacity:0.2}#mermaid-svg-8vopoyGDkRf90ox0 .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-8vopoyGDkRf90ox0 .section2{fill:#fff400}#mermaid-svg-8vopoyGDkRf90ox0 .section1,#mermaid-svg-8vopoyGDkRf90ox0 .section3{fill:#fff;opacity:0.2}#mermaid-svg-8vopoyGDkRf90ox0 .sectionTitle0{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .sectionTitle1{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .sectionTitle2{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .sectionTitle3{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-8vopoyGDkRf90ox0 .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .grid path{stroke-width:0}#mermaid-svg-8vopoyGDkRf90ox0 .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-8vopoyGDkRf90ox0 .task{stroke-width:2}#mermaid-svg-8vopoyGDkRf90ox0 .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .taskText:not([font-size]){font-size:11px}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-8vopoyGDkRf90ox0 .task.clickable{cursor:pointer}#mermaid-svg-8vopoyGDkRf90ox0 .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-8vopoyGDkRf90ox0 .taskText0,#mermaid-svg-8vopoyGDkRf90ox0 .taskText1,#mermaid-svg-8vopoyGDkRf90ox0 .taskText2,#mermaid-svg-8vopoyGDkRf90ox0 .taskText3{fill:#fff}#mermaid-svg-8vopoyGDkRf90ox0 .task0,#mermaid-svg-8vopoyGDkRf90ox0 .task1,#mermaid-svg-8vopoyGDkRf90ox0 .task2,#mermaid-svg-8vopoyGDkRf90ox0 .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutside0,#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutside2{fill:#000}#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutside1,#mermaid-svg-8vopoyGDkRf90ox0 .taskTextOutside3{fill:#000}#mermaid-svg-8vopoyGDkRf90ox0 .active0,#mermaid-svg-8vopoyGDkRf90ox0 .active1,#mermaid-svg-8vopoyGDkRf90ox0 .active2,#mermaid-svg-8vopoyGDkRf90ox0 .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-8vopoyGDkRf90ox0 .activeText0,#mermaid-svg-8vopoyGDkRf90ox0 .activeText1,#mermaid-svg-8vopoyGDkRf90ox0 .activeText2,#mermaid-svg-8vopoyGDkRf90ox0 .activeText3{fill:#000 !important}#mermaid-svg-8vopoyGDkRf90ox0 .done0,#mermaid-svg-8vopoyGDkRf90ox0 .done1,#mermaid-svg-8vopoyGDkRf90ox0 .done2,#mermaid-svg-8vopoyGDkRf90ox0 .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-8vopoyGDkRf90ox0 .doneText0,#mermaid-svg-8vopoyGDkRf90ox0 .doneText1,#mermaid-svg-8vopoyGDkRf90ox0 .doneText2,#mermaid-svg-8vopoyGDkRf90ox0 .doneText3{fill:#000 !important}#mermaid-svg-8vopoyGDkRf90ox0 .crit0,#mermaid-svg-8vopoyGDkRf90ox0 .crit1,#mermaid-svg-8vopoyGDkRf90ox0 .crit2,#mermaid-svg-8vopoyGDkRf90ox0 .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-8vopoyGDkRf90ox0 .activeCrit0,#mermaid-svg-8vopoyGDkRf90ox0 .activeCrit1,#mermaid-svg-8vopoyGDkRf90ox0 .activeCrit2,#mermaid-svg-8vopoyGDkRf90ox0 .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-8vopoyGDkRf90ox0 .doneCrit0,#mermaid-svg-8vopoyGDkRf90ox0 .doneCrit1,#mermaid-svg-8vopoyGDkRf90ox0 .doneCrit2,#mermaid-svg-8vopoyGDkRf90ox0 .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-8vopoyGDkRf90ox0 .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-8vopoyGDkRf90ox0 .milestoneText{font-style:italic}#mermaid-svg-8vopoyGDkRf90ox0 .doneCritText0,#mermaid-svg-8vopoyGDkRf90ox0 .doneCritText1,#mermaid-svg-8vopoyGDkRf90ox0 .doneCritText2,#mermaid-svg-8vopoyGDkRf90ox0 .doneCritText3{fill:#000 !important}#mermaid-svg-8vopoyGDkRf90ox0 .activeCritText0,#mermaid-svg-8vopoyGDkRf90ox0 .activeCritText1,#mermaid-svg-8vopoyGDkRf90ox0 .activeCritText2,#mermaid-svg-8vopoyGDkRf90ox0 .activeCritText3{fill:#000 !important}#mermaid-svg-8vopoyGDkRf90ox0 .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-8vopoyGDkRf90ox0 g.classGroup text .title{font-weight:bolder}#mermaid-svg-8vopoyGDkRf90ox0 g.clickable{cursor:pointer}#mermaid-svg-8vopoyGDkRf90ox0 g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-8vopoyGDkRf90ox0 g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-8vopoyGDkRf90ox0 .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-8vopoyGDkRf90ox0 .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-8vopoyGDkRf90ox0 .dashed-line{stroke-dasharray:3}#mermaid-svg-8vopoyGDkRf90ox0 #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 .commit-id,#mermaid-svg-8vopoyGDkRf90ox0 .commit-msg,#mermaid-svg-8vopoyGDkRf90ox0 .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-8vopoyGDkRf90ox0 g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-8vopoyGDkRf90ox0 g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-8vopoyGDkRf90ox0 g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-8vopoyGDkRf90ox0 .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-8vopoyGDkRf90ox0 .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-8vopoyGDkRf90ox0 .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-8vopoyGDkRf90ox0 .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-8vopoyGDkRf90ox0 .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-8vopoyGDkRf90ox0 .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-8vopoyGDkRf90ox0 .edgeLabel text{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-8vopoyGDkRf90ox0 .node circle.state-start{fill:black;stroke:black}#mermaid-svg-8vopoyGDkRf90ox0 .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-8vopoyGDkRf90ox0 #statediagram-barbEnd{fill:#9370db}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-state .divider{stroke:#9370db}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-8vopoyGDkRf90ox0 .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-8vopoyGDkRf90ox0 .note-edge{stroke-dasharray:5}#mermaid-svg-8vopoyGDkRf90ox0 .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-8vopoyGDkRf90ox0 .error-icon{fill:#522}#mermaid-svg-8vopoyGDkRf90ox0 .error-text{fill:#522;stroke:#522}#mermaid-svg-8vopoyGDkRf90ox0 .edge-thickness-normal{stroke-width:2px}#mermaid-svg-8vopoyGDkRf90ox0 .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-8vopoyGDkRf90ox0 .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-8vopoyGDkRf90ox0 .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-8vopoyGDkRf90ox0 .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-8vopoyGDkRf90ox0 .marker{fill:#333}#mermaid-svg-8vopoyGDkRf90ox0 .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-8vopoyGDkRf90ox0 { 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; } A B C D E F G H

依定义，显然路径覆盖方式不唯一，上图可被这些路径覆盖$\{AEFD,BC,FG\}$，也可被这些路径覆盖$\{ABCD,EF,GH\}$，当然也可以这样覆盖$\{AB,CD,AE,FD,GH\}$。

可以看出，区分不同路径覆盖的一个很重要的指标是整个覆盖集合的路径数。于是我们引出最小路径覆盖的概念，即路径数最小的覆盖。

如何求得最小路径覆盖？在没看相关知识时我脑补了一个算法：从出度最多的点开始BFS分层，再从入度最多的点开始按反图分层，然后DFS贪心找两个层数差最多的点取路径。不过随即发现自己的脑补跟脑瘫无异，随意构造一个特殊的图即可卡掉：

#mermaid-svg-YSESI9WIu0EMzeXj .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-YSESI9WIu0EMzeXj .label text{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .node rect,#mermaid-svg-YSESI9WIu0EMzeXj .node circle,#mermaid-svg-YSESI9WIu0EMzeXj .node ellipse,#mermaid-svg-YSESI9WIu0EMzeXj .node polygon,#mermaid-svg-YSESI9WIu0EMzeXj .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-YSESI9WIu0EMzeXj .node .label{text-align:center;fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .node.clickable{cursor:pointer}#mermaid-svg-YSESI9WIu0EMzeXj .arrowheadPath{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-YSESI9WIu0EMzeXj .flowchart-link{stroke:#333;fill:none}#mermaid-svg-YSESI9WIu0EMzeXj .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-YSESI9WIu0EMzeXj .edgeLabel rect{opacity:0.9}#mermaid-svg-YSESI9WIu0EMzeXj .edgeLabel span{color:#333}#mermaid-svg-YSESI9WIu0EMzeXj .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-YSESI9WIu0EMzeXj .cluster text{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj 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-YSESI9WIu0EMzeXj .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-YSESI9WIu0EMzeXj text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-YSESI9WIu0EMzeXj .actor-line{stroke:grey}#mermaid-svg-YSESI9WIu0EMzeXj .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-YSESI9WIu0EMzeXj .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-YSESI9WIu0EMzeXj #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-YSESI9WIu0EMzeXj .sequenceNumber{fill:#fff}#mermaid-svg-YSESI9WIu0EMzeXj #sequencenumber{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj #crosshead path{fill:#333;stroke:#333}#mermaid-svg-YSESI9WIu0EMzeXj .messageText{fill:#333;stroke:#333}#mermaid-svg-YSESI9WIu0EMzeXj .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-YSESI9WIu0EMzeXj .labelText,#mermaid-svg-YSESI9WIu0EMzeXj .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-YSESI9WIu0EMzeXj .loopText,#mermaid-svg-YSESI9WIu0EMzeXj .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-YSESI9WIu0EMzeXj .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-YSESI9WIu0EMzeXj .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-YSESI9WIu0EMzeXj .noteText,#mermaid-svg-YSESI9WIu0EMzeXj .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-YSESI9WIu0EMzeXj .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSESI9WIu0EMzeXj .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSESI9WIu0EMzeXj .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSESI9WIu0EMzeXj .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .section{stroke:none;opacity:0.2}#mermaid-svg-YSESI9WIu0EMzeXj .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-YSESI9WIu0EMzeXj .section2{fill:#fff400}#mermaid-svg-YSESI9WIu0EMzeXj .section1,#mermaid-svg-YSESI9WIu0EMzeXj .section3{fill:#fff;opacity:0.2}#mermaid-svg-YSESI9WIu0EMzeXj .sectionTitle0{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .sectionTitle1{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .sectionTitle2{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .sectionTitle3{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-YSESI9WIu0EMzeXj .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .grid path{stroke-width:0}#mermaid-svg-YSESI9WIu0EMzeXj .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-YSESI9WIu0EMzeXj .task{stroke-width:2}#mermaid-svg-YSESI9WIu0EMzeXj .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .taskText:not([font-size]){font-size:11px}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-YSESI9WIu0EMzeXj .task.clickable{cursor:pointer}#mermaid-svg-YSESI9WIu0EMzeXj .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSESI9WIu0EMzeXj .taskText0,#mermaid-svg-YSESI9WIu0EMzeXj .taskText1,#mermaid-svg-YSESI9WIu0EMzeXj .taskText2,#mermaid-svg-YSESI9WIu0EMzeXj .taskText3{fill:#fff}#mermaid-svg-YSESI9WIu0EMzeXj .task0,#mermaid-svg-YSESI9WIu0EMzeXj .task1,#mermaid-svg-YSESI9WIu0EMzeXj .task2,#mermaid-svg-YSESI9WIu0EMzeXj .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutside0,#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutside2{fill:#000}#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutside1,#mermaid-svg-YSESI9WIu0EMzeXj .taskTextOutside3{fill:#000}#mermaid-svg-YSESI9WIu0EMzeXj .active0,#mermaid-svg-YSESI9WIu0EMzeXj .active1,#mermaid-svg-YSESI9WIu0EMzeXj .active2,#mermaid-svg-YSESI9WIu0EMzeXj .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-YSESI9WIu0EMzeXj .activeText0,#mermaid-svg-YSESI9WIu0EMzeXj .activeText1,#mermaid-svg-YSESI9WIu0EMzeXj .activeText2,#mermaid-svg-YSESI9WIu0EMzeXj .activeText3{fill:#000 !important}#mermaid-svg-YSESI9WIu0EMzeXj .done0,#mermaid-svg-YSESI9WIu0EMzeXj .done1,#mermaid-svg-YSESI9WIu0EMzeXj .done2,#mermaid-svg-YSESI9WIu0EMzeXj .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-YSESI9WIu0EMzeXj .doneText0,#mermaid-svg-YSESI9WIu0EMzeXj .doneText1,#mermaid-svg-YSESI9WIu0EMzeXj .doneText2,#mermaid-svg-YSESI9WIu0EMzeXj .doneText3{fill:#000 !important}#mermaid-svg-YSESI9WIu0EMzeXj .crit0,#mermaid-svg-YSESI9WIu0EMzeXj .crit1,#mermaid-svg-YSESI9WIu0EMzeXj .crit2,#mermaid-svg-YSESI9WIu0EMzeXj .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-YSESI9WIu0EMzeXj .activeCrit0,#mermaid-svg-YSESI9WIu0EMzeXj .activeCrit1,#mermaid-svg-YSESI9WIu0EMzeXj .activeCrit2,#mermaid-svg-YSESI9WIu0EMzeXj .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-YSESI9WIu0EMzeXj .doneCrit0,#mermaid-svg-YSESI9WIu0EMzeXj .doneCrit1,#mermaid-svg-YSESI9WIu0EMzeXj .doneCrit2,#mermaid-svg-YSESI9WIu0EMzeXj .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-YSESI9WIu0EMzeXj .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-YSESI9WIu0EMzeXj .milestoneText{font-style:italic}#mermaid-svg-YSESI9WIu0EMzeXj .doneCritText0,#mermaid-svg-YSESI9WIu0EMzeXj .doneCritText1,#mermaid-svg-YSESI9WIu0EMzeXj .doneCritText2,#mermaid-svg-YSESI9WIu0EMzeXj .doneCritText3{fill:#000 !important}#mermaid-svg-YSESI9WIu0EMzeXj .activeCritText0,#mermaid-svg-YSESI9WIu0EMzeXj .activeCritText1,#mermaid-svg-YSESI9WIu0EMzeXj .activeCritText2,#mermaid-svg-YSESI9WIu0EMzeXj .activeCritText3{fill:#000 !important}#mermaid-svg-YSESI9WIu0EMzeXj .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-YSESI9WIu0EMzeXj g.classGroup text .title{font-weight:bolder}#mermaid-svg-YSESI9WIu0EMzeXj g.clickable{cursor:pointer}#mermaid-svg-YSESI9WIu0EMzeXj g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-YSESI9WIu0EMzeXj g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-YSESI9WIu0EMzeXj .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-YSESI9WIu0EMzeXj .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-YSESI9WIu0EMzeXj .dashed-line{stroke-dasharray:3}#mermaid-svg-YSESI9WIu0EMzeXj #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj .commit-id,#mermaid-svg-YSESI9WIu0EMzeXj .commit-msg,#mermaid-svg-YSESI9WIu0EMzeXj .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-YSESI9WIu0EMzeXj g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-YSESI9WIu0EMzeXj g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-YSESI9WIu0EMzeXj g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-YSESI9WIu0EMzeXj .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-YSESI9WIu0EMzeXj .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-YSESI9WIu0EMzeXj .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-YSESI9WIu0EMzeXj .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-YSESI9WIu0EMzeXj .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-YSESI9WIu0EMzeXj .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-YSESI9WIu0EMzeXj .edgeLabel text{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSESI9WIu0EMzeXj .node circle.state-start{fill:black;stroke:black}#mermaid-svg-YSESI9WIu0EMzeXj .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-YSESI9WIu0EMzeXj #statediagram-barbEnd{fill:#9370db}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-state .divider{stroke:#9370db}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-YSESI9WIu0EMzeXj .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-YSESI9WIu0EMzeXj .note-edge{stroke-dasharray:5}#mermaid-svg-YSESI9WIu0EMzeXj .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-YSESI9WIu0EMzeXj .error-icon{fill:#522}#mermaid-svg-YSESI9WIu0EMzeXj .error-text{fill:#522;stroke:#522}#mermaid-svg-YSESI9WIu0EMzeXj .edge-thickness-normal{stroke-width:2px}#mermaid-svg-YSESI9WIu0EMzeXj .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-YSESI9WIu0EMzeXj .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-YSESI9WIu0EMzeXj .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-YSESI9WIu0EMzeXj .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-YSESI9WIu0EMzeXj .marker{fill:#333}#mermaid-svg-YSESI9WIu0EMzeXj .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-YSESI9WIu0EMzeXj { 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; } A B C D E

大致的思想就是贪心取最长链，但我的方法显然跟这相差甚远。为何还在此记下这一脑瘫想法，大抵是想记录下自己还存有对未知的好奇心、探索心，脑子还尚未停转罢（抑起来了）。

转二分图模型

我们关注一个特殊的性质，即对于一个可行的覆盖，其中任意点的入度和出度只有可能取得$0$或$1$。换言之就是如果我们把覆盖画成图，一个点不可能有两条或以上的入边或出边，由此我们想到，我们不妨将一个点拆成两个点，一个是出口，一个是入口，严格点来说，就是如果有$(A,B)$，那么我们就在二分图上连接$(A,B^{\prime })$。就拿我们上面这个特殊图举例，我们进行拆点：

#mermaid-svg-IMh6YSqx4wUu3GpL .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .label text{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .node rect,#mermaid-svg-IMh6YSqx4wUu3GpL .node circle,#mermaid-svg-IMh6YSqx4wUu3GpL .node ellipse,#mermaid-svg-IMh6YSqx4wUu3GpL .node polygon,#mermaid-svg-IMh6YSqx4wUu3GpL .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-IMh6YSqx4wUu3GpL .node .label{text-align:center;fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .node.clickable{cursor:pointer}#mermaid-svg-IMh6YSqx4wUu3GpL .arrowheadPath{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-IMh6YSqx4wUu3GpL .flowchart-link{stroke:#333;fill:none}#mermaid-svg-IMh6YSqx4wUu3GpL .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-IMh6YSqx4wUu3GpL .edgeLabel rect{opacity:0.9}#mermaid-svg-IMh6YSqx4wUu3GpL .edgeLabel span{color:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-IMh6YSqx4wUu3GpL .cluster text{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL 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-IMh6YSqx4wUu3GpL .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-IMh6YSqx4wUu3GpL text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-IMh6YSqx4wUu3GpL .actor-line{stroke:grey}#mermaid-svg-IMh6YSqx4wUu3GpL .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-IMh6YSqx4wUu3GpL #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .sequenceNumber{fill:#fff}#mermaid-svg-IMh6YSqx4wUu3GpL #sequencenumber{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL #crosshead path{fill:#333;stroke:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .messageText{fill:#333;stroke:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-IMh6YSqx4wUu3GpL .labelText,#mermaid-svg-IMh6YSqx4wUu3GpL .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-IMh6YSqx4wUu3GpL .loopText,#mermaid-svg-IMh6YSqx4wUu3GpL .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-IMh6YSqx4wUu3GpL .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-IMh6YSqx4wUu3GpL .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-IMh6YSqx4wUu3GpL .noteText,#mermaid-svg-IMh6YSqx4wUu3GpL .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-IMh6YSqx4wUu3GpL .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-IMh6YSqx4wUu3GpL .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-IMh6YSqx4wUu3GpL .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-IMh6YSqx4wUu3GpL .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .section{stroke:none;opacity:0.2}#mermaid-svg-IMh6YSqx4wUu3GpL .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-IMh6YSqx4wUu3GpL .section2{fill:#fff400}#mermaid-svg-IMh6YSqx4wUu3GpL .section1,#mermaid-svg-IMh6YSqx4wUu3GpL .section3{fill:#fff;opacity:0.2}#mermaid-svg-IMh6YSqx4wUu3GpL .sectionTitle0{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .sectionTitle1{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .sectionTitle2{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .sectionTitle3{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-IMh6YSqx4wUu3GpL .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .grid path{stroke-width:0}#mermaid-svg-IMh6YSqx4wUu3GpL .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-IMh6YSqx4wUu3GpL .task{stroke-width:2}#mermaid-svg-IMh6YSqx4wUu3GpL .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .taskText:not([font-size]){font-size:11px}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-IMh6YSqx4wUu3GpL .task.clickable{cursor:pointer}#mermaid-svg-IMh6YSqx4wUu3GpL .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IMh6YSqx4wUu3GpL .taskText0,#mermaid-svg-IMh6YSqx4wUu3GpL .taskText1,#mermaid-svg-IMh6YSqx4wUu3GpL .taskText2,#mermaid-svg-IMh6YSqx4wUu3GpL .taskText3{fill:#fff}#mermaid-svg-IMh6YSqx4wUu3GpL .task0,#mermaid-svg-IMh6YSqx4wUu3GpL .task1,#mermaid-svg-IMh6YSqx4wUu3GpL .task2,#mermaid-svg-IMh6YSqx4wUu3GpL .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutside0,#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutside2{fill:#000}#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutside1,#mermaid-svg-IMh6YSqx4wUu3GpL .taskTextOutside3{fill:#000}#mermaid-svg-IMh6YSqx4wUu3GpL .active0,#mermaid-svg-IMh6YSqx4wUu3GpL .active1,#mermaid-svg-IMh6YSqx4wUu3GpL .active2,#mermaid-svg-IMh6YSqx4wUu3GpL .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-IMh6YSqx4wUu3GpL .activeText0,#mermaid-svg-IMh6YSqx4wUu3GpL .activeText1,#mermaid-svg-IMh6YSqx4wUu3GpL .activeText2,#mermaid-svg-IMh6YSqx4wUu3GpL .activeText3{fill:#000 !important}#mermaid-svg-IMh6YSqx4wUu3GpL .done0,#mermaid-svg-IMh6YSqx4wUu3GpL .done1,#mermaid-svg-IMh6YSqx4wUu3GpL .done2,#mermaid-svg-IMh6YSqx4wUu3GpL .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-IMh6YSqx4wUu3GpL .doneText0,#mermaid-svg-IMh6YSqx4wUu3GpL .doneText1,#mermaid-svg-IMh6YSqx4wUu3GpL .doneText2,#mermaid-svg-IMh6YSqx4wUu3GpL .doneText3{fill:#000 !important}#mermaid-svg-IMh6YSqx4wUu3GpL .crit0,#mermaid-svg-IMh6YSqx4wUu3GpL .crit1,#mermaid-svg-IMh6YSqx4wUu3GpL .crit2,#mermaid-svg-IMh6YSqx4wUu3GpL .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-IMh6YSqx4wUu3GpL .activeCrit0,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCrit1,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCrit2,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-IMh6YSqx4wUu3GpL .doneCrit0,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCrit1,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCrit2,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-IMh6YSqx4wUu3GpL .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-IMh6YSqx4wUu3GpL .milestoneText{font-style:italic}#mermaid-svg-IMh6YSqx4wUu3GpL .doneCritText0,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCritText1,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCritText2,#mermaid-svg-IMh6YSqx4wUu3GpL .doneCritText3{fill:#000 !important}#mermaid-svg-IMh6YSqx4wUu3GpL .activeCritText0,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCritText1,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCritText2,#mermaid-svg-IMh6YSqx4wUu3GpL .activeCritText3{fill:#000 !important}#mermaid-svg-IMh6YSqx4wUu3GpL .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-IMh6YSqx4wUu3GpL g.classGroup text .title{font-weight:bolder}#mermaid-svg-IMh6YSqx4wUu3GpL g.clickable{cursor:pointer}#mermaid-svg-IMh6YSqx4wUu3GpL g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-IMh6YSqx4wUu3GpL g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-IMh6YSqx4wUu3GpL .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-IMh6YSqx4wUu3GpL .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-IMh6YSqx4wUu3GpL .dashed-line{stroke-dasharray:3}#mermaid-svg-IMh6YSqx4wUu3GpL #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL .commit-id,#mermaid-svg-IMh6YSqx4wUu3GpL .commit-msg,#mermaid-svg-IMh6YSqx4wUu3GpL .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-IMh6YSqx4wUu3GpL g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-IMh6YSqx4wUu3GpL g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-IMh6YSqx4wUu3GpL g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-IMh6YSqx4wUu3GpL .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-IMh6YSqx4wUu3GpL .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-IMh6YSqx4wUu3GpL .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-IMh6YSqx4wUu3GpL .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-IMh6YSqx4wUu3GpL .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-IMh6YSqx4wUu3GpL .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-IMh6YSqx4wUu3GpL .edgeLabel text{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IMh6YSqx4wUu3GpL .node circle.state-start{fill:black;stroke:black}#mermaid-svg-IMh6YSqx4wUu3GpL .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-IMh6YSqx4wUu3GpL #statediagram-barbEnd{fill:#9370db}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-state .divider{stroke:#9370db}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-IMh6YSqx4wUu3GpL .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-IMh6YSqx4wUu3GpL .note-edge{stroke-dasharray:5}#mermaid-svg-IMh6YSqx4wUu3GpL .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-IMh6YSqx4wUu3GpL .error-icon{fill:#522}#mermaid-svg-IMh6YSqx4wUu3GpL .error-text{fill:#522;stroke:#522}#mermaid-svg-IMh6YSqx4wUu3GpL .edge-thickness-normal{stroke-width:2px}#mermaid-svg-IMh6YSqx4wUu3GpL .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-IMh6YSqx4wUu3GpL .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-IMh6YSqx4wUu3GpL .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-IMh6YSqx4wUu3GpL .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-IMh6YSqx4wUu3GpL .marker{fill:#333}#mermaid-svg-IMh6YSqx4wUu3GpL .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-IMh6YSqx4wUu3GpL { 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; } A B C D E A' B' C' D' E'

因为是用mermaid直接画的图，可能不像对称分布的图那么美观，不过勉强可🐛。显然上面的二分图的最大匹配是$4$，其中一个可行最大匹配为$\{(A,D^{\prime }),(D,B^{\prime }),(B,C^{\prime }),(C,E^{\prime })\}$，观察上面这个集合，这点非常重要。我们发现其实他就是一条路径$ADBCE$，而我们的最小路径覆盖的路径数应该为$1$，正好为点数-最大匹配，这是否是巧合呢？显然不是。

首先对于DAG来说，因为无环，所以拆点后的二分图不可能取得全匹配，否则必然成环。那么我们不妨来研究一下“失配”的成因。

对于一条简单有向路径，它中间的节点有一条入边，一条出边，表现在二分图里就是它在右部的点有入边，在左部的点有出边。而对于两端的节点，显然起点在右部无入边，终点在左部无出边。这些中间的点总是跟它的前后节点成串联。那么就是说，一旦原图中存在一条路径，若在二分图中进行相应的匹配，则一定会在左部和右部分别产生一个孤立的节点，或者我们说产生了一对孤立的节点（终点和起点’）。而点数-匹配数正好就是孤立点对数，因此其显然就是在当前匹配情况下还原到原图中的路径数。既然我们要求原图的最小路径覆盖，那门我们只需令匹配数最大，即我们的最小路径覆盖=点数-最大匹配数。

由是我们可以将最小路径覆盖问题转化为在拆点的二分图上做最大匹配。