題目鏈接: poj 2516
題目大意: 給出N間商店和它們對K種商品的需求，再給出M個供應商和K種商品的庫存
然後再給出第x種商品從j供應商運輸到i商店的單位運輸費用
求N間商店對商品的需求能否得到滿足，並且輸出最小費用
解題思路: 如果直接建圖會超時，因為頂點數太多
所以根據每種商品，進行K次最小費用流：
1.建立超級源點，源點指向N間商店，容...
閱讀全文
題目鏈接: poj 3614
題目大意: 給出N個區間，然後M個數，每個數最多可以匹配Ki次
問最多有多少個區間能被匹配
解題思路: 若按區間起點從小到大開始排，每個數按從小到大開始排
下面這種情況會過不了
1 9 6
2 6 9
既會出現k2可以同時匹配X1和X2，但k2隻能匹配X1，若選擇k1匹配x1則結果是錯誤的...
閱讀全文
題目鏈接: poj 3281
題目大意: 有N頭奶牛，A種食物和B種飲料，每頭奶牛都有自己喜歡的食物和飲料
問有最多有多少頭奶牛既可以得到自己喜歡的食物又可以得到喜歡的飲料
解題思路: 開始沒有把奶牛分成兩個點，這樣會導致幾種食物流入同一頭奶牛
正確的構圖:
1.建立超級源點，源點分別指向A種不同的食物，容量為1
2.建立超級匯點，B種不同的飲料...
閱讀全文
題目鏈接: poj 2337
題目大意: 給出N個單詞，單詞A的開頭與另外單詞B結尾相同
則單詞A和單詞B可以連起來，問是否可以把所有單詞都串成一條線
輸出最小字典序的(按單詞的字典序串)
解題思路: 對於每個單詞，把單詞的起點和終點字母當作頂點
這個單詞即是起點到終點的一條單向邊
根據有向圖的歐拉圖判斷，若頂點的出度-入度為0，或者一個為1一個...
閱讀全文
題目鏈接: poj 1041
題目大意: 給出無向圖，每條邊有唯一的序號
是否存在歐拉迴路，若存在輸出邊序號最小字典序的路徑
解題思路: 無向歐拉迴路的判斷方法，若存在奇數度點，則不存在歐拉迴路
依據靜態鄰接鏈表的特性，從序號大到小建立邊
因為這樣總能保證序號最小的邊首先訪問到
PS:歐拉路徑的問題要記得判斷圖是否聯通
代碼:
#include <...
閱讀全文
題目鏈接: poj 3422
題目大意: 給出NxN的數字矩陣，左上角走到右下角(只能向右或向下走)，sum記錄走過點值的和
走過的點值置為0，問走K次，求sum的最大值
解題思路: 開始想到的是K次最長路，結果WA了
因為每次走最長路會導致下次走的時候不是最優解
建立費用流模型，把每個頂點T，分成兩個頂點T和T''
因為要限制每個頂點的值只加一次，T->T...
閱讀全文
題目鏈接:
poj 1088
題目大意: 給出NxM的矩陣，每個點的值都不同
若某點四個方向中某個方向的值比它小則可以移動，求能夠走的最長步數
解題思路: 經典的狀態壓縮Dp，Dp[ x ][ y ]記錄從(x , y)點出發能走的最長步數
Dp[ x ][ y ]=Max(Dp[ x ][ y ]，DFS(xx , yy) + 1)
若某個點之前已經走過，則不用再走，直接返回之前所能走到的最大值
代碼:
#include <stdi...
閱讀全文