二分图【模板】
二分圖：原圖G的頂點(diǎn)可以分類兩個集合X和Y，所有的邊關(guān)聯(lián)的兩個頂點(diǎn)恰好一個屬于集合X，另一個屬于集合Y，則稱該圖為二分圖。?
二分圖匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點(diǎn)，即一個頂點(diǎn)最多只有一條邊。則稱M是一個匹配。?
二分圖最大匹配：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。?
二分圖完美匹配：如果所有點(diǎn)都在匹配邊上，則稱這個最大匹配是完美匹配。?
二分圖多重匹配：二分圖匹配一對一匹配，這里允許集合Y中的一個元素和集合X中的多個元素匹配(一般有最大限制N)，但是集合X中的元素只能和集合Y中的多個元素匹配。?
二分圖最佳匹配：將二分圖加權(quán)，在圖中找到一個總權(quán)值最大的匹配。?
二分圖最小點(diǎn)覆蓋： 最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點(diǎn)關(guān)聯(lián)。?
二分圖最小點(diǎn)覆蓋 = 二分圖最大匹配?
二分圖最小邊覆蓋：選擇最少的邊，使得能夠覆蓋圖中所有的點(diǎn)。?
二分圖最小邊覆蓋 = 無向圖被重復(fù)計(jì)算兩次，ans = N - 最大匹配數(shù)/2?
DAG圖的最小路徑覆蓋：用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖?
(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。?
最小路徑覆蓋 ＝ 節(jié)點(diǎn)數(shù)N－最大匹配數(shù)?
二分圖的最大獨(dú)立集：在Ｎ個點(diǎn)的圖G中選出若干個點(diǎn)，使這若干個點(diǎn)兩兩之間沒有邊，求點(diǎn)數(shù)最大值。?
二分圖的最大獨(dú)立集數(shù) = 節(jié)點(diǎn)數(shù)（n）— 最大匹配數(shù)（m）?
一般是雙向邊，則被重復(fù)計(jì)算了兩次，ans = N - 最大匹配數(shù)/2
二分圖最大匹配——匈牙利算法DFS版：
<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXN = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">220</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool</span> Map[MAXN][MAXN]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool</span> bMask[MAXN]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> NX,NY; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> cx[MAXN],cy[MAXN]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> FindPath(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NY; ++i) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Map[u][i] && !bMask[i]) { bMask[i] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(cy[i] == -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span> || FindPath(cy[i])) { cy[i] = u; cx[u] = i; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; } } } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MaxMatch() { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> res = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NX; ++i) cx[i] = -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NY; ++i) cy[i] = -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NX; ++i) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(cx[i] == -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NY; ++j) bMask[j] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; res += FindPath(i); } } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> res; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//返回最大匹配數(shù)</span> } </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li><li style="box-sizing: border-box; padding: 0px 5px;">41</li><li style="box-sizing: border-box; padding: 0px 5px;">42</li><li style="box-sizing: border-box; padding: 0px 5px;">43</li><li style="box-sizing: border-box; padding: 0px 5px;">44</li><li style="box-sizing: border-box; padding: 0px 5px;">45</li></ul>二分圖多重匹配：
<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXN = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">33</span>; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//最大頂點(diǎn)數(shù)</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Map[MAXN][MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//二分圖</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool</span> Mask[MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//尋找增廣路徑時(shí)的標(biāo)志數(shù)組</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> NX,NY,N; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//NX左集合頂點(diǎn)數(shù)，NY右集合頂點(diǎn)數(shù)</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> vcy[MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//vcy[i]表示右集合i頂點(diǎn)匹配到左集合的頂點(diǎn)數(shù)目</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> cy[MAXN][MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//cy[i][j]表示與右集合i頂點(diǎn)匹配的第j個元素</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> limit[MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//每個右集合各頂點(diǎn)最多匹配左集合頂點(diǎn)的個數(shù)</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//也可以為limit，表示最多匹配左集合頂點(diǎn)的共同限制數(shù)，如果為待求元素，可二分搜索查找答案</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool</span> FindPath(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//尋找增廣路徑</span> {<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">5</span>; ++i){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Map[u][i] && !Mask[i]){Mask[i] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(vcy[i] < limit[i]) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//vcy[i] < limit</span>{cy[i][vcy[i]++] = u;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">true</span>;}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; j < vcy[i]; ++j) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//j < vcy[i]</span>{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(FindPath(cy[i][j])){cy[i][j] = u;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">true</span>;}}}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">false</span>; }<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> MulMatch() <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求多重匹配</span> {<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Ans = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(vcy,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(vcy));<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= N; ++i){<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(Mask,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(Mask));Ans += FindPath(i); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//計(jì)算右邊能匹配點(diǎn)個數(shù)</span><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">/*if(!FindPath(i))return false;*/</span>}<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//return true;</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Ans == N)<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"T-shirts rock!\n"</span>);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"I'd rather not wear a shirt anyway...\n"</span>); }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li><li style="box-sizing: border-box; padding: 0px 5px;">41</li><li style="box-sizing: border-box; padding: 0px 5px;">42</li><li style="box-sizing: border-box; padding: 0px 5px;">43</li><li style="box-sizing: border-box; padding: 0px 5px;">44</li><li style="box-sizing: border-box; padding: 0px 5px;">45</li><li style="box-sizing: border-box; padding: 0px 5px;">46</li><li style="box-sizing: border-box; padding: 0px 5px;">47</li><li style="box-sizing: border-box; padding: 0px 5px;">48</li><li style="box-sizing: border-box; padding: 0px 5px;">49</li><li style="box-sizing: border-box; padding: 0px 5px;">50</li><li style="box-sizing: border-box; padding: 0px 5px;">51</li><li style="box-sizing: border-box; padding: 0px 5px;">52</li><li style="box-sizing: border-box; padding: 0px 5px;">53</li><li style="box-sizing: border-box; padding: 0px 5px;">54</li><li style="box-sizing: border-box; padding: 0px 5px;">55</li><li style="box-sizing: border-box; padding: 0px 5px;">56</li><li style="box-sizing: border-box; padding: 0px 5px;">57</li></ul>二分圖最佳匹配——KM算法：
<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<iostream></span> <span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<algorithm></span> <span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<cstdio></span> <span class="hljs-preprocessor" style="color: rgb(68, 68, 68); box-sizing: border-box;">#include<cstring></span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">using</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">namespace</span> <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">std</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXN = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">330</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> INF = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0xffffff0</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N,NX,NY; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> link[MAXN],lx[MAXN],ly[MAXN],slack[MAXN]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> visx[MAXN],visy[MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//標(biāo)記</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Map[MAXN][MAXN]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//存放權(quán)值</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//lx[],ly[]頂標(biāo); link[]記錄匹配值</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> FindPath(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//回溯尋找最優(yōu)解</span> {visx[u] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NY; ++i){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(visy[i])<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">continue</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> temp = lx[u] + ly[i] - Map[u][i];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(temp == <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>)<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//if(Map[u][i] == lx[u] + ly[i]) //說明是相等子圖</span>{visy[i] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(link[i] == -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span> || FindPath(link[i])){link[i] = u;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(slack[i] > temp)slack[i] = temp;}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; }<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> KM() <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求權(quán)值最大的最佳匹配</span> {<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(ly,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(ly));<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(link,-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(link));<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NX; ++i){lx[i] = -INF; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求最小權(quán)匹配則 lx[i] = INF</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NY; ++j)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Map[i][j] > lx[i]) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//最小權(quán)匹配則更改符號</span>lx[i] = Map[i][j];}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NX; ++i){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NY; ++j)slack[j] = INF;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span>(<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>){<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(visx,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(visx));<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">memset</span>(visy,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">sizeof</span>(visy));<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(FindPath(i))<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">break</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> d = INF;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NY; ++j)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(!visy[j] && d > slack[j])d = slack[j];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(d == INF)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> ;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NX; ++j)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(visx[j])lx[j] -= d; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求最小權(quán)值則改為 lx[j] += d;</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= NY; ++j)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(visy[j])ly[j] += d; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//求最小權(quán)值則改為 ly[j] -= d;</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span>slack[j] -= d;}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> res = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= NY; ++i)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(link[i] > -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>)res += Map[link[i]][i];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> res; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//輸出最佳匹配的最大權(quán)值和</span> }<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> main() {<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span>(~<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">scanf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d"</span>,&N)){NX = NY = N;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= N; ++i)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= N; ++j)<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">scanf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d"</span>,&Map[i][j]);<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d\n"</span>,KM());}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; }</code>總結(jié)
- 上一篇： K短路【模板】
- 下一篇： 差分约束系统【模板】