水题
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 51 6 #define M 100001 7 #define INF 1e9 8 #define min(x, y) ((x) < (y) ? (x) : (y)) 9 10 int n, k, s, t, cnt, tot, sum; 11 int head[M], to[M], val[M], cost[M], next[M], dis[M], pre[M], a[N][N], b[N][N]; 12 bool vis[M]; 13 14 inline int read() 15 { 16 int x = 0, f = 1; 17 char ch = getchar(); 18 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 19 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 20 return x * f; 21 } 22 23 inline void add2(int x, int y, int z, int c) 24 { 25 to[cnt] = y; 26 val[cnt] = z; 27 cost[cnt] = c; 28 next[cnt] = head[x]; 29 head[x] = cnt++; 30 } 31 32 inline void add(int x, int y, int z, int c) 33 { 34 add2(x, y, z, c); 35 add2(y, x, 0, -c); 36 } 37 38 inline bool spfa() 39 { 40 int i, u, v; 41 std::queue <int> q; 42 memset(vis, 0, sizeof(vis)); 43 memset(pre, -1, sizeof(pre)); 44 memset(dis, 127 / 3, sizeof(dis)); 45 q.push(s); 46 dis[s] = 0; 47 while(!q.empty()) 48 { 49 u = q.front(), q.pop(); 50 vis[u] = 0; 51 for(i = head[u]; i ^ -1; i = next[i]) 52 { 53 v = to[i]; 54 if(val[i] && dis[v] > dis[u] + cost[i]) 55 { 56 dis[v] = dis[u] + cost[i]; 57 pre[v] = i; 58 if(!vis[v]) 59 { 60 q.push(v); 61 vis[v] = 1; 62 } 63 } 64 } 65 } 66 return pre[t] ^ -1; 67 } 68 69 int main() 70 { 71 int i, j, x, d; 72 n = read(); 73 k = read(); 74 s = 0, t = (n * n << 1) + 1; 75 memset(head, -1, sizeof(head)); 76 for(i = 1; i <= n; i++) 77 for(j = 1; j <= n; j++) 78 { 79 x = read(), b[i][j] = ++tot; 80 add(b[i][j], b[i][j] + n * n, 1, -x); 81 add(b[i][j], b[i][j] + n * n, INF, 0); 82 } 83 for(i = 1; i <= n; i++) 84 for(j = 1; j <= n; j++) 85 { 86 if(i < n) add(b[i][j] + n * n, b[i + 1][j], INF, 0); 87 if(j < n) add(b[i][j] + n * n, b[i][j + 1], INF, 0); 88 } 89 add(s, 1, k, 0); 90 add(n * n << 1, t, k, 0); 91 while(spfa()) 92 { 93 d = INF; 94 for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) d = min(d, val[i]); 95 for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) 96 { 97 val[i] -= d; 98 val[i ^ 1] += d; 99 } 100 sum += dis[t] * d; 101 } 102 printf("%d ", -sum); 103 return 0; 104 }