Kaka's Matrix Travels
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 Ktravels.
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
3 2
1 2 3
0 2 1
1 4 2
Sample Output
15
Source
POJ Monthly--2007.10.06, Huang, Jinsong
题目类型：最小费用最大流
算法分析：建图时需要拆点，将每个点A拆成点A’和点A”，从A’向A”先连一条容量为1，花费为该点值的有向边，再连一条容量为k-1，花费为0的有向边(第一条边表示第一次到达该位置时可以拿走cost价值的东西，第二条边表示该点在拿完之后没有了，但是可以走k-1步)。若A点存在右边相邻或者是下面相邻的点B，则从A”向B’连一条容量为k，花费为0的有向边。最后再分别建一个源点和汇点，源点和1”相连容量为k，花费为0，2*n*n + 1和汇点相连容量为k，花费为0。最后跑一个最小费用流即可。注意这里边表的个数！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
/************************************************* Author :supermaker Created Time :2016/4/1 20:26:51 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 6000 + 66; struct Node { int to, nxt, c, f, cost; }; Node edge[maxn*6]; int head[maxn], edgelen; void Init () { memset (head, -1, sizeof (head)); memset (edge, -1, sizeof (edge)); edgelen = 0; } void AddEdge (int cost, int u, int v, int w, int rw = 0) { edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0; edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++; edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0; edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++; } int dis[maxn], cnt[maxn], inq[maxn], par[maxn]; int N; bool spfa (int s, int e) { for (int i = 0; i <= N; i++) { dis[i] = INF; inq[i] = cnt[i] = 0; par[i] = -1; } dis[s] = 0; queue <int> qu; qu.push (s); inq[s]++, cnt[s]++; while (!qu.empty ()) { int u = qu.front (); qu.pop (); inq[u]--; if (cnt[u] > N) { DB ("hi"); return false; } for (int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost) { dis[v] = dis[u] + edge[i].cost; par[v] = i; if (!inq[v]) { qu.push (v); inq[v]++, cnt[v]++; } } } } if (par[e] == -1) return false; return true; } int allcost; int MinCostMaxFlow (int s, int e) { int res = 0; allcost = 0; while (spfa (s, e)) { int minval = INF; for (int i = par[e]; i != -1; i = par[edge[i^1].to]) minval = min (minval, edge[i].c - edge[i].f); for (int i = par[e]; i != -1; i = par[edge[i^1].to]) { edge[i].f += minval; edge[i^1].f -= minval; allcost += edge[i].cost * minval; } res += minval; //DB (res); } return res; } int g[66][66]; int main() { //CFF; //CPPFF; int n, k; while (scanf ("%d%d", &n, &k) != EOF) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf ("%d", &g[i][j]); Init (); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { int u = (i - 1) * n + j; AddEdge (-g[i][j], u, u + n * n, 1); AddEdge (0, u, u + n * n, k - 1); if (i + 1 <= n) AddEdge (0, u + n * n, u + n, k); if (j + 1 <= n) AddEdge (0, u + n * n, u + 1, k); //DB (u), DB (u + n * n); } AddEdge (0, 0, 1, k); AddEdge (0, 2 * n * n, 2 * n * n + 1, k); N = 2 * n * n + 2; MinCostMaxFlow (0, 2 * n * n + 1); printf ("%d\n", -allcost); } return 0; } |