定義見：OI-Wiki 圖的匹配 。

二分圖

解法 \(1\) ：網(wǎng)絡(luò)流(通用)

二分圖最大匹配可以轉(zhuǎn)換成最大流(費(fèi)用流)模型 。

如果使用 \(\operatorname{Dinic}\) 算法求該網(wǎng)絡(luò)的最大流，復(fù)雜度\(O(\sqrt{n}m)\) 。

具體代碼見博客文章網(wǎng)絡(luò)流 。

解法 \(2\) ：匈牙利算法(一般只適合求二分圖最大匹配)

即不斷尋找增廣路，遍歷二分圖，最壞復(fù)雜度為 \(O(nm)\) 。

P3386 【模板】二分圖最大匹配 ：

核心代碼：

bool dfs(int x) {for(int i=hea[x];i;i=nex[i]) if(!vis[ver[i]]){vis[ver[i]]=true;if(!match[ver[i]] || dfs(match[ver[i]])){match[ver[i]]=x; return true;}}return false; }for(int i=1;i<=n;i++) {memset(vis,false,sizeof(vis));if(dfs(i)) ans++; }

CF1139E Maximize Mex

參考

性質(zhì)：

二分圖最大獨(dú)立集

選最多的點(diǎn)，滿足兩兩之間沒有邊相連。

二分圖中，\(\text{最大獨(dú)立集} = n - \text{最大匹配}\) 。

二分圖最小點(diǎn)覆蓋

選最少的點(diǎn)，滿足每條邊至少有一個(gè)端點(diǎn)被選，不難發(fā)現(xiàn)補(bǔ)集是獨(dú)立集。

二分圖中，\(\text{最小點(diǎn)覆蓋} = n - \text{最大獨(dú)立集}\) 。

---

一般圖

咕咕咕~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的图的匹配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。