題意

題目鏈接

分析

• 考慮每個(gè)棋子對(duì)對(duì)應(yīng)的橫向縱向的極大區(qū)間的影響：記之前這個(gè)區(qū)間中的點(diǎn)數(shù)為 \(x\) ，那么此次多配對(duì)的數(shù)量即 \(x\) 。
• 考慮費(fèi)用流，\(S\rightarrow 橫向區(qū)間 \rightarrow 棋盤上的點(diǎn) \rightarrow 縱向區(qū)間 \rightarrow T\) ，其中 $S\rightarrow 橫向區(qū)間 $ 和 \(縱向區(qū)間 \rightarrow T\) 的費(fèi)用差分設(shè)置。
• 如何尋找答案？如果采用 \(spfa\) 的增廣方式的話，每次增廣到終點(diǎn)的每條流量的費(fèi)用是相同的，且每個(gè)點(diǎn)用1的流量表示，所以在進(jìn)行費(fèi)用流的過程中可以統(tǒng)計(jì) \(k\) 為所有值的答案。

代碼鏈接

轉(zhuǎn)載于:https://www.cnblogs.com/yqgAKIOI/p/10269982.html

總結(jié)

以上是生活随笔為你收集整理的[LOJ#6068]. 「2017 山东一轮集训 Day4」棋盘[费用流]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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