前提

通常對偶圖建立在平面圖之上

平面圖：單邊除端點外無交點

解決范圍

求平面圖的最大流

做法

平面圖顯然在邊的基礎上分成了若干個塊，每個塊由一個結點來維護

在邊緣出與源點匯點聯通，中間處結點之間相互聯通

連的邊容量為該邊穿過原圖的邊的值，如有方向性則由原圖的方向性決定

例題

[NOI2010]海拔

轉載于:https://www.cnblogs.com/y2823774827y/p/10924490.html

總結

以上是生活随笔為你收集整理的对偶图小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。