萌新刚学OI,WA45pts求调QwQ
查看原帖
萌新刚学OI,WA45pts求调QwQ
520056
luoyx楼主2023/8/4 15:46
#include <bits/stdc++.h>
using namespace std;
int r,c,d;
int a[55][55],id[55][55],cnt,res;
int sum;
char C;
int b[55][55],id2[55][55];
int s,t;
int u,v,w;
const int N=500005;
int head[N],ecnt=1;
struct edge{
	int v,w,nxt;
}e[N<<1];

void add(int u,int v,int w){
	e[++ecnt].v=v;
	e[ecnt].nxt=head[u];
	e[ecnt].w=w;
	head[u]=ecnt;
	swap(u,v);
	e[++ecnt].v=v;
	e[ecnt].nxt=head[u];
	e[ecnt].w=0;
	head[u]=ecnt;
}

int dep[N],vis[N],maxflow;
int bfs(){
	memset(dep,0x3f,sizeof(dep));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(s);
	dep[s]=0;
	while(!q.empty()){
		//cout<<114514<<'\n';
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dep[v]>dep[u]+1&&e[i].w){
				dep[v]=dep[u]+1;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	if(dep[t]>1e6) return 0;
	return 1;
}
int cur[N];
int dfs(int u,int flow){
	int rflow=0;
	if(u==t) return flow;//cout<<1919810<<'\n';
	for(int i=cur[u];i;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v;
		if(e[i].w&&dep[u]+1==dep[v]){
			rflow=dfs(v,min(flow,e[i].w));
			if(rflow==0) continue;  
			e[i].w-=rflow;
			e[i^1].w+=rflow;
			return rflow;
		}
	}
	return 0;
}
int dinic(){
	int lowflow=0;
	while(bfs()){
		for(int i=1;i<=50000;i++) cur[i]=head[i];
		while(lowflow=dfs(s,0x3f3f3f3f)) maxflow+=lowflow;
	}
	return maxflow;
}

bool dis(int a,int b,int c,int d){
	return (double)sqrt((a-c)*(a-c)+(b-d)*(b-d))<=(double)d*1.0;
}

signed main(){
	cin>>r>>c>>d;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>C;
			a[i][j]=(int)(C-'0');
			if(a[i][j]>0){
				id[i][j]=++cnt;
			}
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(a[i][j]>0){
				add(id[i][j],id[i][j]+cnt,a[i][j]);
			}
		}
	}
	res=cnt;
	cnt*=2;
	s=++cnt,t=++cnt;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>C;
			if(C=='L'){
				b[i][j]=1;
				sum++;
				id2[i][j]=++cnt;
				add(s,id[i][j],1);
			} 
			else b[i][j]=0;
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(!id[i][j]) continue;
			for(int p=1;p<=r;p++){
				for(int q=1;q<=c;q++){
					if(!id[p][q]) continue;
					if(dis(i,j,p,q)){
						add(id[i][j]+res,id[p][q],0x3f3f3f3f);
					} 
				}
			}
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(id[i][j]&&(i<=d||r-i+1<=d||j<=d||c-j+1<=d)){
				add(id[i][j]+res,t,0x3f3f3f3f);
			}
		}
	}
	cout<<sum-dinic();
}
2023/8/4 15:46
加载中...