[luogu_P2045]方格取数加强版
试题描述
给出一个 \(n \times n\) 的矩阵,每一格有一个非负整数 \(A_{i,j},(A_{i,j} \le 1000)\) 现在从 \((1,1)\) 出发,可以往右或者往下走,最后到达 \((n,n)\),每达到一格,把该格子的数取出来,该格子的数就变成 \(0\),这样一共走 \(K\) 次,现在要求 \(K\) 次所达到的方格的数的和最大
输入
第一行两个数 \(n,k\)（\(1 \le n \le 50, 0 \le k \le 10\)）
接下来 \(n\) 行,每行 \(n\) 个数,分别表示矩阵的每个格子的数
输出
一个数,为最大和
输入示例
3 11 2 30 2 11 4 2
输出示例
11
数据规模及约定
见“试题描述”和“输入”
题解
网格图拆点后建边，源点到 \((1, 1)\) 容量限制为 \(k\)，跑最小费用最大流。
假设点 \(i\) 拆成 \(in_i\) 和 \(out_i\)，则在 \(in_i\) 和 \(out_i\) 之间连两条边，一条容量为 \(1\)，费用为对应方格中的数的相反数，另一条容量无穷费用为 \(0\)。
#include#include #include #include #include #include #include using namespace std;#define rep(i, s, t) for(int i = (s); i <= (t); i++)#define dwn(i, s, t) for(int i = (s); i >= (t); i--)int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 5010#define maxm 40010#define oo 2147483647struct Edge { int from, to, flow, cost; Edge() {} Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), flow(_3), cost(_4) {}};struct ZKW { int n, m, s, t, cost, ans, head[maxn], nxt[maxm]; Edge es[maxm]; int d[maxn]; deque Q; bool inq[maxn]; bool vis[maxn]; void init() { m = 0; memset(head, -1, sizeof(head)); return ; } void setn(int _) { n = _; return ; } void AddEdge(int a, int b, int c, int d) { es[m] = Edge(a, b, c, d); nxt[m] = head[a]; head[a] = m++; es[m] = Edge(b, a, 0, -d); nxt[m] = head[b]; head[b] = m++; return ; } bool BFS() { rep(i, 1, n) d[i] = oo; d[t] = 0; Q.push_back(t); inq[t] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop_front(); inq[u] = 0; for(int i = head[u]; i != -1; i = nxt[i]) { Edge& e = es[i^1]; if(d[e.from] > d[u] + e.cost && e.flow) { d[e.from] = d[u] + e.cost; if(!inq[e.from]) { inq[e.from] = 1; if(Q.empty() || d[e.from] <= d[Q.front()]) Q.push_front(e.from); else Q.push_back(e.from); } } } } if(d[s] == oo) return 0; cost = d[s]; return 1; } int DFS(int u, int a) { if(u == t || !a) return ans += cost * a, a; if(vis[u]) return 0; vis[u] = 1; int flow = 0, f; for(int i = head[u]; i != -1; i = nxt[i]) { Edge& e = es[i]; if(d[e.to] == d[u] - e.cost && (f = DFS(e.to, min(a, e.flow)))) { flow += f; a -= f; e.flow -= f; es[i^1].flow += f; if(!a) return flow; } } return flow; } int MaxFlow(int _s, int _t) { s = _s; t = _t; int flow = 0, f; while(BFS()) do { memset(vis, 0, sizeof(vis)); f = DFS(s, oo); flow += f; } while(f); return flow; }} sol;#define maxr 55int CntP;struct Point { int id; Point(): id(0) {} int p() { return id ? id : id = ++CntP; }} In[maxr][maxr], Out[maxr][maxr], S, T;int main() { int n = read(), k = read(); sol.init(); sol.AddEdge(S.p(), In[1][1].p(), k, 0); sol.AddEdge(Out[n][n].p(), T.p(), oo, 0); rep(i, 1, n) rep(j, 1, n) { sol.AddEdge(In[i][j].p(), Out[i][j].p(), 1, -read()); sol.AddEdge(In[i][j].p(), Out[i][j].p(), oo, 0); if(i < n) sol.AddEdge(Out[i][j].p(), In[i+1][j].p(), oo, 0); if(j < n) sol.AddEdge(Out[i][j].p(), In[i][j+1].p(), oo, 0); } sol.setn(CntP); sol.MaxFlow(S.p(), T.p()); printf("%d\n", -sol.ans); return 0;}