bzoj5403 marshland

bzoj5403 marshland

原题传送门:>Here<

看到这个数据范围,果断选择网络流。

我们发现消掉偶数点是没有意义的,所以问题可以转化为:

每消掉一个奇数点,需要消掉两个互为对角的偶数点。

我们看到每次消掉两个点,考虑可以使一个点连源点,另一个点连汇点。

所以我们的算法就是:

  • 从源点向偶数行的偶数点连边;

  • 从偶数行的偶数点向相邻奇数点连边;

  • 从奇数点向相邻奇数行的偶数点连边;
  • 从奇数行的偶数点向汇点连边。

同时为了维护费用,奇数点需要拆点。

(偶数点其实是不需要拆点的,然而我脑残了。。。)

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

int head[400001],nxt[3000001],b[3000001],k=1,n,m,K,map[101][101],v[400001],c[3000001],S,S1,T,h,t,q[10000001],dis[400001],pre[400001],ans;
bool vis[101][101],inq[400001];
void push(int s,int t,int val,int cost){
nxt[++k]=head[s];
head[s]=k;
b[k]=t;
v[k]=val;
c[k]=cost;
}
void link(int s,int t,int val,int cost){
push(s,t,val,cost);
push(t,s,0,-cost);
}
int hsh(int x,int y){
return (x-1)*n+y;
}
bool spfa(){
for(int i=S+1;i<=T;i++)dis[i]=-10000000000000000ll;
memset(inq,0,sizeof inq);
h=t=0;
dis[S]=0;
q[++t]=S;
inq[S]=1;
while(h<t){
inq[q[++h]]=0;
for(int i=head[q[h]];i;i=nxt[i])
if((v[i]>0)&&dis[b[i]]<(dis[q[h]]+c[i])){
dis[b[i]]=dis[q[h]]+c[i];
pre[b[i]]=i;
if(!inq[b[i]])inq[b[i]]=1,q[++t]=b[i];
}
}
return dis[T]>0;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&K);
S=0,S1=2*n*n+1,T=S1+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&map[i][j]),ans+=map[i][j];
for(int i=1,t1,t2;i<=K;i++){
scanf("%lld%lld",&t1,&t2);
vis[t1][t2]=1;
}
link(S,S1,m,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(((i+j)&1)==0){
if((i&1)==0){
link(S1,hsh(i,j),0x7f7f7f7f,0);
if(i>1)link(hsh(i,j)+n*n,hsh(i-1,j),0x7f7f7f7f,0);
if(j>1)link(hsh(i,j)+n*n,hsh(i,j-1),0x7f7f7f7f,0);
if(i<n)link(hsh(i,j)+n*n,hsh(i+1,j),0x7f7f7f7f,0);
if(j<n)link(hsh(i,j)+n*n,hsh(i,j+1),0x7f7f7f7f,0);
}
else{
link(hsh(i,j)+n*n,T,0x7f7f7f7f,0);
if(i>1)link(hsh(i-1,j)+n*n,hsh(i,j),0x7f7f7f7f,0);
if(j>1)link(hsh(i,j-1)+n*n,hsh(i,j),0x7f7f7f7f,0);
if(i<n)link(hsh(i+1,j)+n*n,hsh(i,j),0x7f7f7f7f,0);
if(j<n)link(hsh(i,j+1)+n*n,hsh(i,j),0x7f7f7f7f,0);
}
if(!vis[i][j])link(hsh(i,j),hsh(i,j)+n*n,1,0);
}
else{
if(!vis[i][j])link(hsh(i,j),hsh(i,j)+n*n,1,map[i][j]);
}
while(spfa()){
int tem=T;
while(tem!=S){
v[pre[tem]]--;
v[pre[tem]^1]++;
tem=b[pre[tem]^1];
}
ans-=dis[T];
}
printf("%lld",ans);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×