[2018HN省队集训D5T1] 沼泽地marshland
题意
给定一张 \(n\times n\) 的棋盘, 对于位置 \((x,y)\), 若 \(x+y\) 为奇数则可能有一个正权值. 你可以在棋盘上互不重叠地任意放置最多 \(m\) 个L形三骨牌, 放置后骨牌拐角处的格子权值清零. 其中 \(k\) 个格子是障碍且障碍处权值必定为 \(0\). 最小化权值总和.
\(n\le 50\).
题解
这种乍一看像插头DP但是又让你求最优解而不是计数的棋盘题多半就是网络流了.
首先拐角的地方如果不是带权点的话这张骨牌没卵用, 所以我们只算拐角是带权点的骨牌. 容易发现覆盖一个带权点时必定会覆盖两个共顶点的无权点, 不难想到在无权点之间连权值为对应带权点的边然后跑最大权匹配.
无权点其实也组成了一个网格图(转 \(45^\circ\) 就看出来了), 所以可以黑白染色跑费用流. (实际上就是按奇偶行分类)
但是这样可能会出现重复计算某个带权点的贡献的情况. 所以我们必须要让包含同一个带权点的情况互斥. 只要加一对点在中间连一条容量为 \(1\) 权值为带权点的值的边, 然后再把它周围的点都用这对点收束到一起就好了.
或者说这是个三分图匹配?
建完图限制一下流量不超过 \(m\) 跑最小(大)费用流就好了. 用总和减去覆盖掉的权值.
参考代码
#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++;
}