P2472 [SCOI2007] 蜥蜴全部MLE求大佬帮助!
查看原帖
P2472 [SCOI2007] 蜥蜴全部MLE求大佬帮助!
531207
July14th楼主2024/1/25 11:41
#include<bits/stdc++.h> 
#define ll long long
#define cf(i) e[i].cf
using namespace std;
queue <int> q;
const int maxn=807;
const int maxm=100007;
const int inf=0x7f7f7f7f;
struct Edge{
	int u,v,cf;
}e[maxm];
int first[maxn],tt[maxm],ES=1;
inline void add(int u,int v,int cf){
	e[++ES]=(Edge){u,v,cf};
	tt[ES]=first[u];
	first[u]=ES;
	return ;
}
inline void Add(int u,int v,int cf){
	Add(u,v,cf);Add(v,u,0);
	return ;
}
int N,M,S,T;
char m1[27][27],m2[27][27];
inline int num(int i,int j){
	return (i-1)*M+j;
}
int d,all,ans;
inline void link(int u,int i,int j){
	if(i<1||i>N||j<1||j>M){
		Add(u,T,inf);
		return ;
	}
	if(m1[i][j]=='0') return ;
	Add(u,num(i,j),inf);
	return ;
}
inline void link(int i,int j){
	if(m1[i][j]=='0') return ; 
	Add(num(i,j),num(i,j)+all,m1[i][j]-'0');
	if(m2[i][j]=='L')
		Add(S,num(i,j),1),ans++;
	if(i==1||j==1||i==N||j==M)
		Add(num(i,j)+all,T,inf);
	int u=num(i,j)+all;
	if(d>=1){
		link(u,i-1,j);link(u,i+1,j);
		link(u,i,j-1);link(u,i,j+1);
	}
	if(d>=2){
		link(u,i-2,j);link(u,i+2,j);
		link(u,i,j-2);link(u,i,j+2);
		link(u,i-1,j-1);link(u,i-1,j+1);
		link(u,i+1,j-1);link(u,i+1,j+1);
	}
	if(d>=3){
		link(u,i-3,j);link(u,i+3,j);link(u,i,j-3);link(u,i,j+3);
		link(u,i-2,j-2);link(u,i-2,j+2);link(u,i+2,j-2);link(u,i+2,j+2);
		link(u,i-1,j-2);link(u,i-1,j+2);link(u,i+1,j-2);link(u,i+1,j+2);
		link(u,i-2,j-1);link(u,i-2,j+1);link(u,i+2,j-1);link(u,i+2,j+1);
	}
	if(d>=4){
		link(u,i-4,j);link(u,i+4,j);link(u,i,j-4);link(u,i,j+4);
		link(u,i-1,j-3);link(u,i-1,j+3);link(u,i+1,j-3);link(u,i+1,j+3);
		link(u,i-3,j-1);link(u,i-3,j+1);link(u,i+3,j-1);link(u,i+3,j+1);
		link(u,i-3,j-2);link(u,i-3,j+2);link(u,i+3,j-2);link(u,i+3,j+2);
		link(u,i-2,j-3);link(u,i-2,j+3);link(u,i+2,j-3);link(u,i+2,j+3);
	}
	return ;
}
int cur[maxn],cnt[maxn];
inline bool BFS(){
	memset(cnt,0,sizeof(cnt));
	cnt[S]=1;
	q.push(S);
	int u,v;
	while(!q.empty()){
		u=q.front();q.pop();
		for(register int i=first[u];i;i=tt[i]){
			v=e[i].v;
			if(cf(i)>0&&!cnt[v]){
				cnt[v]=cnt[u]+1;
				q.push(v);
			}
		}
	}
	return cnt[T]!=0;
}
inline int dfs(int u,int f){
	if(u==T) return f;
	int d,v,sum=0;
	for(register int &i=cur[u];i;i=tt[i]){
		v=e[i].v;
		if(cf(i)>0&&cnt[v]==cnt[u]+1){
			d=dfs(v,min(f,cf(i)));
			if(d>0){
				f-=d;sum+=d;
				cf(i)-=d;cf(i^1)+=d;
				if(f<=0) return sum;
			}
		}
	}
	return sum;
}
int main(){
	scanf("%d%d%d",&N,&M,&d);
    T=N*M*2+1;all=N*M;
	for(register int i=1;i<=N;i++)
		scanf("%s",m1[i]+1);
	for(register int i=1;i<=N;i++)
		scanf("%s",m2[i]+1);
	for(register int i=1;i<=N;i++)
		for(register int j=1;j<=M;j++)
			link(i,j);
	while(BFS()){
		memcpy(cur,first,sizeof(cur));
		ans-=dfs(S,inf);
	}
	printf("%d",ans);
	return 0;
}
2024/1/25 11:41
加载中...