玄关求调 WA on 7
查看原帖
玄关求调 WA on 7
1419569
Z_kazuha楼主2024/12/16 10:01
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int c[51][51];
int n,m,d,nn,s,t,l[N],r[N],ci,head[N<<1],cnt=1;
int id(int x,int y){
	return (x-1)*m+y;
}
struct node{int to,nxt,w;}e[N<<1];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].w=w;
	head[u]=cnt;
}
int jl(int x,int y,int a,int b){
	return (y-b)*(y-b)+(x-a)*(x-a);
}
int now[N],deep[N];
int bfs(){
	for(int i=s;i<=t;i++)deep[i]=inf;
	deep[s]=0;
	now[s]=head[s];
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];~i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].w&&deep[v]==inf){
				q.push(v);
				now[v]=head[v];
				deep[v]=deep[u]+1;
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int sum){
	if(u==t)return sum;
	int k,flow=0;
	for(int i=now[u];~i&&sum;i=e[i].nxt){
		now[u]=i;
		int v=e[i].to;
		if(e[i].w&&(deep[v]==deep[u]+1)){
			k=dfs(v,min(sum,e[i].w));
			if(k==0)deep[v]=inf;
			e[i].w-=k;
			e[i^1].w-=k;
			flow+=k;
			sum-=k;
		}
	}
	return flow;
}
int sum;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>d;
	t=n*m*2+1;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char o;
			cin>>o;
			c[i][j]=o-'0';
			if(c[i][j]){
				l[++ci]=i;
				r[ci]=j;
			}
		}
	}
	nn=n*m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char o;
			cin>>o;
			if(o=='L'){
				add(0,id(i,j),1);
				add(id(i,j),0,0);
				sum++;
			}
		}
	}
	for(int i=1;i<=ci;i++){
		add(id(l[i],r[i]),id(l[i],r[i])+nn,c[l[i]][r[i]]);
		add(id(l[i],r[i])+nn,id(l[i],r[i]),0);
		if(l[i]<=d||r[i]<=d||l[i]+d>n||r[i]+d>m){
			add(id(l[i],r[i])+nn,t,inf);
			add(t,id(l[i],r[i])+nn,0);
		}
	}
	for(int i=1;i<=ci;i++){
		for(int j=1;j<=ci;j++){
			if(d*d>=jl(l[i],r[i],l[j],r[j])&&i!=j){
				add(id(l[i],r[i])+nn,id(l[j],r[j]),inf);
				add(id(l[j],r[j]),id(l[i],r[i])+nn,0);
			}
		}
	}
	int ans=0;
	while(bfs())ans+=dfs(s,inf);
	cout<<sum-ans;
	return 0;
}
2024/12/16 10:01
加载中...