P2045 方格取数加强版
大意
在 \(N \times N\) 的方格上走 \(K\)，走过的地方就变成收益为 \(0\) 的点，求最大收益。
思路
那么我们思考一下，如何处理，首先是，我们要保证的事情是第一次走有收益，那么我们只需要流的时候流量为 \(K\)，这样可以限制次数，那么最后的收益就用花费求，那么如何做到这一点呢？
我们考虑拆点，拆为 in 和 out，那么我们在 in 和 out 间连容量为 \(1\) 的，那么就保证了这个地方只会做一次收益，再连收益为 \(0\) 的边，容量为 \(k - 1\) ，这样下次还能经过，只不过没有收益了，然后就是正常的由 out 点向下面和右边的 in 连边，容量为 \(k\)，花费为 \(0\)，那么就可以正常的走动。
然后对我们建完的这个图跑最小费用最大流。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 5005;
const int MAXM = 40005;
struct node{int u, v, nxt, c, w;
}e[MAXM * 4];int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];
void init(){tot = 0;memset(h, -1, sizeof(h));
}void add(int u, int v, int c, int w){e[tot] = {u, v, h[u], c, w};h[u] = tot ++;e[tot] = {v, u, h[v], 0, -w};h[v] = tot ++;
}bool spfa(){memset(vis, 0, sizeof(vis));memset(d, -1, sizeof(d));memset(pre, -1, sizeof(pre));queue<int> q;q.push(S);d[S] = 0;vis[S] = true;while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c){if(d[v] < d[u] + e[i].w){d[v] = d[u] + e[i].w;pre[v] = i;if(!vis[v]){q.push(v);vis[v] = true;}}}}}return (d[T] != -1);
}int EK(){int res = 0;while(spfa()){int Min = 1e9;for(int i = T;i != S;i = e[pre[i]].u){Min = min(Min, e[pre[i]].c);}for(int i = T;i != S;i = e[pre[i]].u){e[pre[i]].c -= Min;e[pre[i] ^ 1].c += Min;res += e[pre[i]].w * Min;}}return res;
}int n, k;
int a[MAXN][MAXN];int id(int x, int y){return (x - 1) * n + y;
}int main(){// freopen("maze.in", "r", stdin);// freopen("maze.out", "w", stdout);cin >> n >> k;init();for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){cin >> a[i][j];}}for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){int in = id(i, j), out = in + n * n;add(in, out, 1, a[i][j]);add(in, out, k - 1, 0);if(i + 1 <= n){add(out, id(i + 1, j), k, 0);}if(j + 1 <= n){add(out, id(i, j + 1), k, 0);}}}S = 0, T = 2 * n * n + 1;add(S, id(1, 1), k, 0);add(id(n, n) + n * n, T, k, 0);cout << EK() << endl;return 0;
}