想法：
點與點之間的邊是雙向邊，但是走某一邊後另一邊就不能走了，所以我們把一個點i分成兩個點i和i'，i到i'容量為1，點i建圖的時候：
- cap[i][i']=1
- 假設j在i的上方，cap[i'][j]=1，上下左右依此類推
然後我們還要有個super source(S)和super sink(T)，把最外面四個邊的點i'連到T，S連到輸入的座標i(也就是銀行的位置)。建完圖後，就是做最大流看結果是否等於銀行的數量即可。
一開始TLE了，後來用了個vector<int> edge[MAX]來存每個點i能連到哪些點，避免bfs的時候nxt要從0到最後(程式碼81行)，最後時間為1.8s。
Read full article from Programming學習筆記: Maximum Flow
No comments:
Post a Comment