Description

给出一个 \(n*n\) 的矩阵,每一格有一个非负整数 \(A_{i,j}\) ,(\(A_{i,j} <= 1000\))现在从 \((1,1)\) 出发,可以往右或者往下走,最后到达 \((n,n)\) ,每达到一格,把该格子的数取出来,该格子的数就变成 \(0\) ,这样一共走 \(K\) 次,现在要求 \(K\) 次所达到的方格的数的和最大

Solution

一条边 \((a,b)\) 表示容量为 \(a\) ，费用为 \(b\) 。

把每个点拆成两个点，入点和出点。入点用来接受边，出点用来发出边

源点向 \((1,1)\) 连一条边 \((k,0)\) ，\((n,n)\) 向汇点连一条 \((k,0)\) ，表示可以走 \(k\) 次

每个点往他的右和下分别连一条 \((\infty, 0)\) 表示联通关系

每个点的入点与出点之间连两条边 \((1,x)\) 和 \((\infty, 0)\)。\(x\) 是该点的权值。

这是因为每个点只能取一次。

然后跑一遍最大费用最大流就完事啦

小技巧：把费用取负然后跑最小费用最大流

Code

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

const int N = 550;

int n, m, cnt, vis[N * N * 3], dis[N * N * 3];

int S, T, k, pre[N * N * 3], f[N * N * 3];

struct node {

  int d, sid, tid;

}a[N][N];

struct edge {

  int v, w, f; edge *next, *rev;

}pool[N * N * 2], *head[N * N * 3], *r[N * N * 3];

inline void addedge(int u, int v, int f, int w) {

  edge *p = &pool[++cnt], *q = &pool[++cnt];

  p->v = v, p->f = f, p->w = w,  p->next = head[u], head[u] = p; p->rev = q;

  q->v = u, q->f = 0, q->w = -w, q->next = head[v], head[v] = q; q->rev = p;

}

inline bool spfa() {

  for(int i = S; i <= T; i++) r[i] = NULL, dis[i] = INF, vis[i] = 0, pre[i] = -1;

  queue <int> Q; Q.push(S); vis[S] = 1; dis[S] = 0; f[S] = INF;

  while(!Q.empty()) {

    int u = Q.front(); Q.pop(); vis[u] = 0;

    for(edge *p = head[u]; p; p = p->next) {

      int v = p->v;

      if(p->f > 0 && dis[v] > dis[u] + p->w) {

        dis[v] = dis[u] + p->w;

        pre[v] = u, r[v] = p;

        f[v] = min(f[u], p->f);

        if(!vis[v]) vis[v] = 1, Q.push(v);

      }

    }

  }

  return pre[T] != -1;

}

inline int MCMF() {

  int ans = 0;

  while(spfa()) {

    for(int i = T; i != S; i = pre[i]) {

      r[i]->f -= f[T]; r[i]->rev->f += f[T];

    } ans += dis[T] * f[T];

  } return ans;

}

int main() {

  scanf("%d %d", &n, &k); S = 0, T = 2 * n * n + 1;

  addedge(S, 1, k, 0);

  for(int i = 1; i <= n; i++) {

    for(int j = 1; j <= n; j++) {

      int x; scanf("%d", &x);

      int id = (i - 1) * n + j;

      a[i][j].sid = 2 * id - 1;

      a[i][j].tid = 2 * id;

      addedge(a[i][j].sid, a[i][j].tid, 1, -x);

      addedge(a[i][j].sid, a[i][j].tid, INF, 0);

    }

  }

  for(int i = 1; i <= n; i++)

    for(int j = 1; j <= n; j++) {

      if(i < n) addedge(a[i][j].tid, a[i + 1][j].sid, INF, 0);

      if(j < n) addedge(a[i][j].tid, a[i][j + 1].sid, INF, 0);

    }

  addedge(a[n][n].tid, T, k, 0);

  printf("%d\n", -MCMF());

  return 0;

}