POJ 3422 Kaka's Matrix Travels

Kaka's Matrix Travels

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3422
64-bit integer IO format: %lld Java class name: Main

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the K travels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

Sample Output

Source

POJ Monthly--2007.10.06

解题：第一次玩这种拆点的费用流。由于点有费用。而费用流的费用在边上，所以只有把点化成一条线。也就是把一个点拆成两个点。一分为2的点建立两条边？为什么呢？一条表示经过该点（原先没拆的点）的费用，另一条表示不经过。然后再建立到右边和到下边的流量无限，费用为0的边。

建立超级源点到第一个格子的边，流量为m，费用为0.为什么是m呢，因为题目说了，只走m次嘛！同理建立最后一个格子到超级汇点的边。然后AC吧。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 10000;
18 struct arc{
19     int v,w,f,next;
20     arc(int x = 0,int y = 0,int z = 0,int nxt = 0){
21         v = x;
22         w = y;
23         f = z;
24         next = nxt;
25     }
26 };
27 arc e[maxn*20];
28 int head[maxn],p[maxn],d[maxn],S,T,tot;
29 bool in[maxn];
30 int n,m;
31 queue<int>q;
32 void add(int u,int v,int w,int f){
33     e[tot] = arc(v,w,f,head[u]);
34     head[u] = tot++;
35     e[tot] = arc(u,-w,0,head[v]);
36     head[v] = tot++;
37 }
38 bool spfa(){
39     while(!q.empty()) q.pop();
40     for(int i = S; i <= T; i++){
41         d[i] = INF;
42         in[i] = false;
43         p[i] = -1;
44     }
45     d[S] = 0;
46     in[S] = true;
47     q.push(S);
48     while(!q.empty()){
49         int u = q.front();
50         q.pop();
51         in[u] = false;
52         for(int i = head[u]; ~i; i = e[i].next){
53             if(e[i].f > 0 && d[e[i].v] > d[u] + e[i].w){
54                 d[e[i].v] = d[u] + e[i].w;
55                 p[e[i].v] = i;
56                 if(!in[e[i].v]){
57                     q.push(e[i].v);
58                     in[e[i].v] = true;
59                 }
60             }
61         }
62     }
63     return p[T] > -1;
64 }
65 int solve(){
66     int tmp = 0,minV;
67     while(spfa()){
68         minV = INF;
69         for(int i = p[T]; ~i; i = p[e[i^1].v])
70             minV = min(minV,e[i].f);
71         for(int i = p[T]; ~i; i = p[e[i^1].v]){
72             e[i].f -= minV;
73             e[i^1].f += minV;
74             tmp += minV*e[i].w;
75         }
76     }
77     return tmp;
78 }
79 int main() {
80     int tmp;
81     while(~scanf("%d %d",&n,&m)){
82         S = 0;
83         T = n*n*2 + 1;
84         tot = 0;
85         memset(head,-1,sizeof(head));
86         for(int i = 1; i <= n; i++)
87             for(int j = 1; j <= n; j++){
88                 scanf("%d",&tmp);
89                 add(n*(i-1)+j,n*(i-1)+j+n*n,-tmp,1);
90                 add(n*(i-1)+j,n*(i-1)+j+n*n,0,INF);
91                 if(i < n) add(n*(i-1)+j+n*n,n*i+j,0,INF);
92                 if(j < n) add(n*(i-1)+j+n*n,n*(i-1)+j+1,0,INF);
93             }
94         add(S,1,0,m);
95         add(2*n*n,T,0,m);
96         printf("%d
",-solve());
97     }
98     return 0;
99 }

View Code