1 /* 2 poj3422 Kaka's Matrix Travels 3 不知道 k次 dp做為什么不對？？？ 4 看了大牛的代碼，才知道還可以這樣做！ 5 開始沒有理解將a 和 a‘ 之間建立怎樣的兩條邊，導致程序一直陷入死循環，真心花了好長時間，快崩潰了。無語..... 6 題意：有個方陣，每個格子里都有一個非負數，從左上角走到右下角，每次走一步，只能往右或往下走，經過的數字拿走 7 每次都找可以拿到數字和最大的路徑走，走k次，求最大和 8 9 這是 最大費用最大流 問題 每次spfa都找的是一條和最大的路徑 s--到左上角的邊流量是K限制增廣次數 10 11 求最大費用最大流只需要把費用換成相反數，用最小費用最大流求解即可 12 13 14 構圖過程： 15 每個點拆分成兩個 a a' 之間建兩條邊(當然還要建退邊)，分別是 (費用為該點相反數,流量為1) (費用為0,流量為k-1) 16 路過這點時，可以通過前邊那條邊拿到數字， 17 以后再從這兒過，就沒有數字可拿了，走的就是第二條邊 18 19 然后是 沒點向 右和下 建一條邊 費用0，流量k 20 */ 21 #include<iostream> 22 #include<queue> 23 #include<cstring> 24 #include<cstdio> 25 #define N 50000 26 #define M 5005 27 #define Max 0x3f3f3f3f 28 using namespace std; 29 class EDGE 30 { 31 public: 32 int u, v, c, f; 33 int next; 34 }; 35 queue<int>q; 36 EDGE edge[N]; 37 int cap[55][55], n, k; 38 int pre[N], first[N]; 39 int dist[M], vis[M]; 40 int edgeN; 41 int s, t; 42 int maxFlow; 43 44 int spfa() 45 { 46 memset(dist, 0x3f, sizeof(dist)); 47 memset(vis, 0, sizeof(vis)); 48 memset(pre, -1, sizeof(pre)); 49 dist[s]=0; 50 q.push(s); 51 vis[s]=1; 52 while(!q.empty()) 53 { 54 int u=q.front(); 55 q.pop(); 56 vis[u]=0; 57 for(int e=first[u]; e!=-1; e=edge[e].next) 58 { 59 int v=edge[e].v; 60 if(dist[v]>dist[u] + edge[e].c && edge[e].f>0) 61 { 62 dist[v]=dist[u] + edge[e].c; 63 pre[v]=e; 64 if(!vis[v]) 65 { 66 vis[v]=1; 67 q.push(v); 68 } 69 } 70 } 71 } 72 if(dist[t]==Max) 73 return 0; 74 return 1; 75 } 76 77 void updateFlow() 78 { 79 int minF=Max; 80 for(int e=pre[t]; e!=-1; e=pre[edge[e].u]) 81 if(minF>edge[e].f) 82 minF=edge[e].f; 83 for(int e=pre[t]; e!=-1; e=pre[edge[e].u]) 84 { 85 edge[e].f-=minF; 86 edge[e^1].f+=minF; 87 maxFlow+=minF*edge[e].c; 88 } 89 } 90 91 void adde(int u, int v, int c, int f) 92 { 93 edge[edgeN].u=u; edge[edgeN].v=v; 94 edge[edgeN].c=c; edge[edgeN].f=f; 95 edge[edgeN].next=first[u]; first[u]=edgeN++; 96 97 edge[edgeN].u=v; edge[edgeN].v=u; 98 edge[edgeN].c=-c; edge[edgeN].f=0; 99 edge[edgeN].next=first[v]; first[v]=edgeN++; 100 } 101 102 int main() 103 { 104 int i, j; 105 while(scanf("%d%d", &n, &k)!=EOF) 106 { 107 maxFlow=0; 108 edgeN=0; 109 memset(first, -1, sizeof(first)); 110 s=0; t=n*n*2+1; 111 for(i=1; i<=n; ++i) 112 for(j=1; j<=n; ++j) 113 scanf("%d", &cap[i][j]); 114 adde(s, 1, 0, k); 115 for(i=1; i<=n; ++i) 116 for(j=1; j<=n; ++j)//n*n個節點，拆點之后變成2*n*n個節點 117 { 118 int nb=(i-1)*n+j; 119 adde(2*nb-1, 2*nb, -cap[i][j], 1);//注意：a到a`是建立兩條邊，但是兩條邊的費用和容量不一樣 120 adde(2*nb-1, 2*nb, 0, k-1); 121 if(j<n)//向右建圖 122 adde(2*nb, 2*(nb+1)-1, 0, k); 123 if(i<n)//向下建圖 124 adde(2*nb, 2*(nb+n)-1, 0, k); 125 } 126 adde(n*n*2, t, 0, k); 127 128 while(spfa())//建好圖之后，直接調用最小費用最大流模板就好了 129 updateFlow(); 130 printf("%d\n", -maxFlow); 131 } 132 return 0; 133 }
?
)
(示例代碼))
