[费用流] HHHOJ#300. 「湖南省队集训2018 Day5」marshland

考虑网络流,把 \(L\) 形的块看作一条链。

这样的路一定是 \(0\) 位置 \(\to\)\(0\) \(\to\) \(0\) 位置 ,而且两个 \(0\) 位置行号奇偶性不同。

这样就随便建图了,\(S \to\) 奇数行的 \(0 \to\)\(0 \to\) 偶数行的 \(0 \to T\)

建费用流,每增广一次就多放了一块,这样就好了。

还要积累建图经验...

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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
typedef long long LL;
using namespace std;
const int maxn=100005,maxe=100005,tra[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct Edge{
int from,to,flow,cap,cost;
Edge(int t1=0,int t2=0,int t3=0,int t4=0,int t5=0){
from=t1;to=t2;flow=t3;cap=t4;cost=t5;
}
} Es[maxe];
int fir[maxn],nxt[maxe],tot=1;
void add(int x,int y,int z,int c){
Es[++tot]=Edge(x,y,0,z,c);
nxt[tot]=fir[x]; fir[x]=tot;
Es[++tot]=Edge(y,x,0,0,-c);
nxt[tot]=fir[y]; fir[y]=tot;
}
queue<int> que;
int fl[maxn],dis[maxn],pth[maxn],ans;
bool vis[maxn];
bool Find_spfa(int S,int T,LL &MaxFlow,LL &MinCost){
memset(fl,0,sizeof(fl)); fl[S]=1e+9;
memset(dis,63,sizeof(dis)); dis[S]=0;
que.push(S); pth[S]=0;
while(!que.empty()){
int x=que.front(); que.pop(); vis[x]=false;
for(int j=fir[x];j;j=nxt[j])
if(Es[j].cap>Es[j].flow&&dis[x]+Es[j].cost<dis[Es[j].to]){
dis[Es[j].to]=dis[x]+Es[j].cost; pth[Es[j].to]=j;
fl[Es[j].to]=min(fl[x],Es[j].cap-Es[j].flow);
if(!vis[Es[j].to]) vis[Es[j].to]=true, que.push(Es[j].to);
}
}
if(!fl[T]||dis[T]>0) return false;
MaxFlow+=fl[T]; MinCost+=fl[T]*dis[T];
for(int j=pth[T];j;j=pth[Es[j].from]){
Es[j].flow+=fl[T];
Es[j^1].flow-=fl[T];
}
return true;
}
int n,m,K,S,T,N,a[55][55],id[55][55],ban[55][55];
LL sum;
int main(){
scanf("%d%d%d",&n,&m,&K);
N=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]), sum+=a[i][j];
while(K--){
int x,y; scanf("%d%d",&x,&y);
ban[x][y]=true;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i+j)&1) if(!ban[i][j]) id[i][j]=++N, add((N<<1)-1,N<<1,1,-a[i][j]);
N<<=1; S=++N; T=++N;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!((i+j)&1)&&!ban[i][j]){
id[i][j]=++N;
if(i&1){
add(S,N,1,0);
for(int k=0;k<=3;k++){
int x=i+tra[k][0],y=j+tra[k][1];
if(1<=x&&x<=n&&1<=y&&y<=n&&!ban[x][y]) add(N,(id[x][y]<<1)-1,1,0);
}
} else{
add(N,T,1,0);
for(int k=0;k<=3;k++){
int x=i+tra[k][0],y=j+tra[k][1];
if(1<=x&&x<=n&&1<=y&&y<=n&&!ban[x][y]) add((id[x][y]<<1),N,1,0);
}
}
}
LL ans1=0,ans2=0;
for(int i=1;i<=m;i++) if(!Find_spfa(S,T,ans1,ans2)) break;
printf("%lld\n",sum+ans2);
return 0;
}