目录

[2018HN省队集训D5T1] 沼泽地marshland

迁移提示
本文迁移自博客园, 原文链接

[2018HN省队集训D5T1] 沼泽地marshland

题意

给定一张 $n\times n$ 的棋盘, 对于位置 $(x,y)$, 若 $x+y$ 为奇数则可能有一个正权值. 你可以在棋盘上互不重叠地任意放置最多 $m$ 个L形三骨牌, 放置后骨牌拐角处的格子权值清零. 其中 $k$ 个格子是障碍且障碍处权值必定为 $0$. 最小化权值总和.

$n\le 50$.

题解

这种乍一看像插头DP但是又让你求最优解而不是计数的棋盘题多半就是网络流了.

首先拐角的地方如果不是带权点的话这张骨牌没卵用, 所以我们只算拐角是带权点的骨牌. 容易发现覆盖一个带权点时必定会覆盖两个共顶点的无权点, 不难想到在无权点之间连权值为对应带权点的边然后跑最大权匹配.

无权点其实也组成了一个网格图(转 $45^\circ$ 就看出来了), 所以可以黑白染色跑费用流. (实际上就是按奇偶行分类)

但是这样可能会出现重复计算某个带权点的贡献的情况. 所以我们必须要让包含同一个带权点的情况互斥. 只要加一对点在中间连一条容量为 $1$ 权值为带权点的值的边, 然后再把它周围的点都用这对点收束到一起就好了.

或者说这是个三分图匹配?

建完图限制一下流量不超过 $m$ 跑最小(大)费用流就好了. 用总和减去覆盖掉的权值.

参考代码

  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>

const int MAXN=110;
const int MAXV=1e4+10;
const int MAXE=3e5+10;
const int INFI=0x7F7F7F7F;
const int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

struct Edge{
	int from;
	int to;
	int dis;
	int flow;
	Edge* rev;
	Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* top=E;

int n;
int m;
int k;
int dis[MAXV];
bool vis[MAXV];
bool inq[MAXV];
int a[MAXN][MAXN];
int id[MAXN][MAXN];
int idx[MAXN][MAXN];
bool blk[MAXN][MAXN];

int Dinic(int,int);
bool SPFA(int,int);
int DFS(int,int,int);
void Insert(int,int,int,int);

int main(){
	scanf("%d%d%d",&n,&m,&k);
	int sum=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",a[i]+j);
			sum+=a[i][j];
		}
	}
	for(int i=0;i<k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		blk[x][y]=true;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			id[i][j]=++cnt;
			if((i^j)&1)
				idx[i][j]=++cnt;
		}
	}
	int s=0,t=cnt+1,ss=cnt+2;
	Insert(ss,s,0,m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!blk[i][j]){
				if((i^j)&1){
					Insert(id[i][j],idx[i][j],-a[i][j],1);
					for(int k=0;k<4;k++){
						std::pair<int,int> a(i+d[k][0],j+d[k][1]),b(i+d[(k+1)%4][0],j+d[(k+1)%4][1]);
						if(id[a.first][a.second]&&id[b.first][b.second]){
							if(a.first&1){
								Insert(id[a.first][a.second],id[i][j],0,1);
								Insert(idx[i][j],id[b.first][b.second],0,1);
							}
							else{
								Insert(id[b.first][b.second],id[i][j],0,1);
								Insert(idx[i][j],id[a.first][a.second],0,1);
							}
						}
					}
				}
				else{
					if(i&1)
						Insert(s,id[i][j],0,1);
					else
						Insert(id[i][j],t,0,1);
				}
			}
		}
	}
	printf("%d\n",sum+Dinic(ss,t));
	return 0;
}

int Dinic(int s,int t){
	int ans=0;
	while(SPFA(s,t))
		ans+=dis[t]*DFS(s,INFI,t);
	return ans;
}

int DFS(int s,int flow,int t){
	if(s==t||flow<=0)
		return flow;
	int rest=flow;
	vis[s]=true;
	for(Edge* i=head[s];i!=NULL;i=i->next){
		if(i->flow>0&&dis[i->to]==dis[s]+i->dis&&!vis[i->to]){
			int tmp=DFS(i->to,std::min(rest,i->flow),t);
			rest-=tmp;
			i->flow-=tmp;
			i->rev->flow+=tmp;
		}
	}
	return flow-rest;
}

bool SPFA(int s,int t){
	memset(dis,0x7F,sizeof(dis));
	memset(vis,0,sizeof(vis));
	std::queue<int> q;
	q.push(s);
	dis[s]=0;
	vis[s]=true;
	while(!q.empty()){
		s=q.front();
		q.pop();
		vis[s]=false;
		for(Edge* i=head[s];i!=NULL;i=i->next){
			if(i->flow>0&&dis[i->to]>dis[s]+i->dis){
				dis[i->to]=dis[s]+i->dis;
				if(!vis[i->to]){
					q.push(i->to);
					vis[i->to]=true;
				}
			}
		}
	}
	return dis[t]<0;
}

inline void Insert(int from,int to,int dis,int flow){
	top->from=from;
	top->to=to;
	top->dis=dis;
	top->flow=flow;
	top->rev=top+1;
	top->next=head[from];
	head[from]=top++;

	top->from=to;
	top->to=from;
	top->dis=-dis;
	top->flow=0;
	top->rev=top-1;
	top->next=head[to];
	head[to]=top++;
}

https://pic.rvalue.moe/2021/08/02/1885eee89fd16.jpg