天天看點

什麼是網絡流的割?什麼是網絡流的最小割?

   前一向學會最大流的幾個寫法~~FF..EK...Dinic...就以為自己會網絡流了...今天去做hh大牛的網絡流習題...發現自己除了最大流....建圖以及其他性質神馬的都一片空白....拿到一個題..無從下手來建圖....網上搜了一下網絡流的建圖政策與方法...很多大牛提到最小割...我知道求最小割求出最大流就行了...最大流和最小割的值是相等的...但我一直沒搞懂最小割是什麼...網上搜了一些最小割的資料....都比較含糊....後來去Google了一個英文資料....幾張圖讓我一下明白網絡流的割是個什麼東西...:

a

繼續閱讀