描述

http://www.lydsy.com/JudgeOnline/problem.php?id=1001

---

分析

這是道經(jīng)典的對偶圖問題, 平面圖最大流問題可以轉(zhuǎn)化為其對偶圖的最短路問題.

轉(zhuǎn)化的方法就是將每個(gè)三角形區(qū)域看作是一個(gè)點(diǎn), 如果兩個(gè)三角形區(qū)域有公共線, 就在兩個(gè)結(jié)點(diǎn)之間連一條權(quán)值為公共線容量的邊.

關(guān)于編號問題我定義了一個(gè)id數(shù)組. 表示以點(diǎn) (x(0~n-2), y(0~m-2)) 為左上角的三角形區(qū)域的編號. 右上三角的編號為id[x][y], 右下為id[x][y]^1.

對偶圖問題還是不太懂.
一開始我認(rèn)為應(yīng)該建立無向圖, MLE多次后改為有向圖. 但兩個(gè)三角之間是豎向邊的情況該從誰向誰連呢? 兩種都試了, 發(fā)現(xiàn)竟然都能AC, 但是一個(gè)7296ms一個(gè)1752ms. 求解釋.
后來發(fā)現(xiàn)不和起點(diǎn)或終點(diǎn)相連的豎邊根本不用考慮, 連都不用連就過了. 而且91196kb, 1404ms. 數(shù)據(jù)的問題嗎? 無語~

---

代碼

1752ms

https://code.csdn.net/snippets/606610#snippets0

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 1001] 狼抓兔子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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