15pts求助,HLPP写法。悬关
查看原帖
15pts求助,HLPP写法。悬关
602803
_qingshu_楼主2023/12/15 11:31
include<bits/stdc++.h>
using namespace std;
int n,m,r,c,s,t,sum;
char mp[100][100];
struct edge{
	int to,nxt;
	long long val;
}e[5200010];
int head[5200010],tot=1,h[5200010];
struct cmp{
	inline bool operator ()(int x,int y)const{
		return h[x]<h[y];
	}
};
priority_queue<int,vector<int>,cmp>qq;
queue<int>q;
long long over[5200010],vist[5200010],gap[5200010];
void add(int u,int v,long long w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].val=w;
	head[u]=tot;
	
	e[++tot].to=u;
	e[tot].nxt=head[v];
	e[tot].val=0;
	head[v]=tot;
}
bool bfs(){
	for(int i=1;i<=2*n*m+2;i++){
		h[i]=1e9;
	}
	h[t]=0;
	q.push(t);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i^1].val&&h[v]>h[x]+1){
				h[v]=h[x]+1;
				q.push(v); 
			}
		}
	}
	return (h[s]!=1e9);
}
void push(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&h[x]==h[v]+1){
			int k=min(over[x],e[i].val);
			e[i].val-=k;
			e[i^1].val+=k;
			over[x]-=k;
			over[v]+=k;
			if(v!=s&&v!=t&&!vist[v]){
				vist[v]=1;
				qq.push(v);
			}
			if(!over[x]){
				return;
			}
		}
	}
}
void relable(int x){
	h[x]=1e9;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&h[x]>h[v]+1){
			h[x]=h[v]+1;
		}
	}
}
long long hlpp(){
	if(!bfs()){
		return 0;
	}
	h[s]=2*n*m+2;
	for(int i=1;i<=2*n*m+2;i++){
		if(h[i]!=1e9){
			gap[h[i]]++;
		}
	}
	for(int i=head[s];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&h[v]!=1e9){
			e[i^1].val=e[i].val;
			over[v]=e[i].val;
			e[i].val=0;
			if(v!=s&&v!=t&&!vist[v]){
				vist[v]=1;
				qq.push(v);
			}
		}
	}
	while(!qq.empty()){
		int x=qq.top();
		qq.pop();
		vist[x]=0;
		push(x);
		if(over[x]){
			gap[h[x]]--;
			if(!gap[h[x]]){
				for(int i=1;i<=2*n*m+2;i++){
					if(i!=t&&i!=s&&h[i]<=2*n*m+2&&h[i]>h[x]){
						h[i]=2*n*m+2+1;
					}
				}
			}
			relable(x);
			gap[h[x]]++;
			vist[x]=1;
			qq.push(x);
		}
	}
	return over[t];
}
int main(){
	cin>>n>>m>>r>>c;
	s=2*n*m+1;
	t=2*n*m+2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			sum+=(mp[i][j]=='.');
		}
	}
	int cx[]={c, c, r,r};
	int cy[]={r,-r,-c,c};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			add(s,(i-1)*m+j,1);
			add((i-1)*m+j+n*m,t,1);
			if(mp[i][j]=='.'){
				for(int k=0;k<4;k++){
					int nowx=i+cx[k],nowy=j+cy[k];
					if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m&&mp[nowx][nowy]=='.'){
						add((i-1)*m+j,(nowx-1)*m+nowy+n*m,1); 
					}
				}
			}
		}
	}
	cout<<sum-hlpp();
}
2023/12/15 11:31
加载中...