P2045

发表于 分类于
方格取数加强版

方格取数加强版

把每个格子拆成两个点，分别为入点和出点。

入点向出点连两条边，一条是容量为 1，费用为 $a_{i,j}$ 的边，表示一个数只能取一次；另一条边容量是 $k-1$，费用为 0，表示这个格子的数取走之后还能经过 $k-1$　次。

然后出点向下面和右面两个格子的入点各连一条边，容量为 $k$，费用 0，表示可以走 $k$ 次。

然后跑最大费用最大流即可。

时间复杂度 $O(n^6)$。

实际上很难跑满所以很轻松就过掉了。。。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll inf=(1ll<<31)-1,N=5e3,M=3e5;

ll n,k,tot,s,t,maxflow,mincost;
ll ver[M*2+5],nxt[M*2+5],edge[M*2+5],wt[M*2+5],head[N+5];
ll dist[N+5],incf[N+5],pre[N+5];
ll a[N+5][N+5];
bool vis[N+5];

inline bool SPFA() {
  queue<ll> q;
  memset(vis,0,sizeof(vis));
  for(ll i=1;i<=2*n*n+2;i++) dist[i]=inf;
  q.push(s);dist[s]=0;vis[s]=1;incf[s]=k;
  while(!q.empty()) {
    ll h=q.front();q.pop();vis[h]=0;
    for(ll i=head[h];i;i=nxt[i]) {
        if(!edge[i]) continue;
        if(dist[ver[i]]>dist[h]+wt[i]) {
          dist[ver[i]]=dist[h]+wt[i];
          incf[ver[i]]=min(incf[h],edge[i]);pre[ver[i]]=i;
          if(!vis[ver[i]]) {vis[ver[i]]=1;q.push(ver[i]);}
        }
    }
  }
  if(dist[t]==inf) return 0;return 1;
}

inline void Update() {
  ll x=t;
  while(x!=s) {
    ll i=pre[x];edge[i]-=incf[t];edge[i^1]+=incf[t];x=ver[i^1];
  }
  maxflow+=incf[t];mincost+=dist[t]*incf[t];
}

inline void Addedge(ll u,ll v,ll c,ll w) {
  ver[++tot]=v;edge[tot]=c;wt[tot]=w;nxt[tot]=head[u];head[u]=tot;
  ver[++tot]=u;edge[tot]=0;wt[tot]=-w;nxt[tot]=head[v];head[v]=tot;
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {

  n=read();k=read();s=2*n*n+1;t=2*n*n+2;

  for(ll i=1;i<=n;i++) {
    for(ll j=1;j<=n;j++) {
        a[i][j]=read();
    }
  }

  tot=1;
  Addedge(s,1,k,0);Addedge(2*n*n,t,k,0);
  for(ll i=1;i<=n;i++) {
    for(ll j=1;j<=n;j++) {
        ll u,v,c,w;
        u=(i-1)*n+j;v=u+n*n;c=1;w=a[i][j];
        Addedge(u,v,c,-w);
        c=k-1;w=0;
        Addedge(u,v,c,-w);
        u=v;v=(i-1)*n+j+1;c=k;w=0;
        if(j!=n) Addedge(u,v,c,-w);
        v=i*n+j;c=k;w=0;
        if(i!=n) Addedge(u,v,c,-w);
    }
  }

  while(SPFA()) {Update();}

  write(-mincost);

  return 0;
}