求助大佬64pts,其余始终RE
查看原帖
求助大佬64pts,其余始终RE
300735
HL_Imrt楼主2024/7/12 16:35
#include<iostream>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
const int N=5050,M=700050,INF=INT_MAX;
int n,m,d,s,t,nm,ans,tot;
int hd[N],cnt=1;
int cur[N],dep[N];
string st[50];
queue<int>qa;
char c;
struct aaa{
	int to,w,nt;
}a[M];
void add(int u,int v,int w){
	a[++cnt].to=v;
	a[cnt].w=w;
	a[cnt].nt=hd[u];
	hd[u]=cnt;
}
void add1(int p,int i,int j,int x){
	if(i>n||i<1||j<1||j>m) add(p,t,x),add(t,p,0);
	else if(st[i][j]!='0') add(p,(i-1)*m+j,x),add((i-1)*m+j,p,0);
}
int bfs(){
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	qa.push(s);
	while(!qa.empty()){
		for(int i=hd[qa.front()];i;i=a[i].nt){
			if(!dep[a[i].to]&&a[i].w>0){
				dep[a[i].to]=dep[qa.front()]+1;
				qa.push(a[i].to);
			}
		}
		qa.pop(); 
	}
	return dep[t];
}
int dfs(int p,int fl){
	if(p==t) return fl;
	int sum=0,fi;
	for(int i=cur[p];i&&sum<fl;i=a[i].nt){
		cur[p]=i;
		if(dep[a[i].to]==dep[p]+1&&a[i].w>0){
			fi=dfs(a[i].to,min(a[i].w,fl-sum));
			sum+=fi,a[i].w-=fi,a[i^1].w+=fi;
		}
	}
	return sum;
}
void Dinic(){
	int x=0;
	while(bfs()){
		memcpy(cur,hd,sizeof(hd));
		x=dfs(s,INF);
		if(x>0) ans+=x;
	}
}
int main(){
	cin>>n>>m>>d;
	nm=n*m,s=2*nm+1,t=2*nm+2;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>st[i][j];
	int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(st[i][j]!='0'){
			    int now=(i-1)*m+j+nm; 
			    x=st[i][j]-'0';
				add((i-1)*m+j,now,x);  
				add(now,(i-1)*m+j,0);  
				for(int l=1;l<=d;l++) add1(now,i,j+l,INF),add1(now,i,j-l,INF),add1(now,i+l,j,INF),add1(now,i-l,j,INF);
				if(d>=2) add1(now,i-1,j-1,INF),add1(now,i-1,j+1,INF),add1(now,i+1,j-1,INF),add1(now,i+1,j+1,INF);
				if(d>=3){
					add1(now,i-1,j-2,INF),add1(now,i-1,j+2,INF),add1(now,i+1,j-2,INF),add1(now,i+1,j+2,INF);
					add1(now,i-2,j-1,INF),add1(now,i-2,j+1,INF),add1(now,i+2,j-1,INF),add1(now,i+2,j+1,INF);
					add1(now,i-2,j-2,INF),add1(now,i-2,j+2,INF),add1(now,i+2,j-2,INF),add1(now,i+2,j+2,INF); 
				}
				if(d==4){
					add1(now,i-1,j-3,INF),add1(now,i-1,j+3,INF),add1(now,i+1,j-3,INF),add1(now,i+1,j+3,INF);
					add1(now,i-3,j-1,INF),add1(now,i-3,j+1,INF),add1(now,i+3,j-1,INF),add1(now,i+3,j+1,INF);
					add1(now,i-2,j-3,INF),add1(now,i-2,j+3,INF),add1(now,i+2,j-3,INF),add1(now,i+2,j+3,INF);
					add1(now,i-3,j-2,INF),add1(now,i-3,j+2,INF),add1(now,i+3,j-2,INF),add1(now,i+3,j+2,INF);
				}
			} 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='L') add(s,(i-1)*m+j,1),add((i-1)*m+j,s,0),++tot;
		}
	}
	Dinic();
	cout<<tot-ans<<endl;
	return 0;
}
2024/7/12 16:35
加载中...