Lvat_s Blog

明显是一个最大流啊……

坑明天填上……

今天是2016年7月31日，我仍然没有填这个坑。

所以，我力争在三天内填好所有的坑(flag)，谢谢各位看我博客的神犇……

长期未填坑表示抱歉……

----------------

说好的填坑来了

我一开始以为是曼哈顿距离，错了好久……

拆点，两点间流量为两点间高度，然后考虑建超级源点连向每个有蜥蜴的柱子上面容量1

所有能跳出的柱子下面向超级汇点连接容量INF

没了

为什么？把蜥蜴看成1的流量模拟一下即可

下面程序中bfs_add为曼哈顿距离的建图

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1005,INF=2100000000;

int r,c,d,h[N],en,level[N],S,T,cur[N],t[25][25],rex,p[N][N];
char mp[N][N];
queue<int> Q;
queue<pair<pair<int,int>,int> > Qx;

struct Edge{
int b,f,next,back;
}e[N*100];

inline int GetID(int x,int y){return (x-1)*c+y;}

inline void AddEdge(int sa,int sb,int sc){
//printf("Line %d %d %d\n",sa,sb,sc);
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline int bfs(){
memset(level,0,sizeof(level));
Q.push(S);level[S]=1;
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && !level[v])level[v]=level[u]+1,Q.push(v);
	}
}
return level[T];
}

int dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int fl,v=e[i].b;
	if(level[v]==level[u]+1 && e[i].f && (fl=dfs(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(!f)return flow;
	}
}
return flow-f;
}

inline int Dinic(){
int ans=0;
while(bfs()){
	for(int i=1;i<=T;i++)cur[i]=h[i];
	ans+=dfs(S,INF);
}
return ans;
}

inline int Abs(const int &x){return x>0?x:-x;}
inline int Dist(const int &x1,const int &y1,const int &x2,const int &y2){return Abs(x2-x1)+Abs(y2-y1);}

/*inline void bfs_add(const int &x,const int &y){
int id=GetID(x,y);
memset(t,0,sizeof(t));
t[x][y]=1;
Qx.push(make_pair(make_pair(x+1,y),d-1));
Qx.push(make_pair(make_pair(x,y+1),d-1));
Qx.push(make_pair(make_pair(x-1,y),d-1));
Qx.push(make_pair(make_pair(x,y-1),d-1));
while(!Qx.empty()){
	pair<pair<int,int>,int> Px=Qx.front();Qx.pop();
	if(Px.first.first<1 || Px.first.first>r || Px.first.second<1 || Px.first.second>c)Px.first.first=0,Px.first.second=0;
	if(t[Px.first.first][Px.first.second])continue;
	t[Px.first.first][Px.first.second]=1;
	//printf("T:%d %d\n",Px.first.first,Px.first.second);
	if(Px.first.first==0 && Px.first.second==0){AddEdge(id+r*c,T,INF);continue;}
	if(p[Px.first.first][Px.first.second])AddEdge(id+r*c,GetID(Px.first.first,Px.first.second),INF);
	if(Px.second==0)continue;
    Qx.push(make_pair(make_pair(Px.first.first+1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second+1),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first-1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second-1),Px.second-1));
}
}*/

inline void Build(){
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(!p[i][j])continue;
		if(i-d<1 || i+d>r || j-d<1 || j+d>c)AddEdge(GetID(i,j)+r*c,T,INF);
		for(int i1=1;i1<=r;i1++){
			for(int j1=1;j1<=c;j1++){
				if(!p[i1][j1] || (i==i1 && j==j1))continue;
				if((i1-i)*(i1-i)+(j1-j)*(j1-j)<=d*d)AddEdge(GetID(i,j)+r*c,GetID(i1,j1),INF);
			}
		}
	}
}
}

int main(){
freopen("1066.in","r",stdin);
freopen("1066.out","w",stdout);
scanf("%d %d %d",&r,&c,&d);
S=2*r*c+1;T=S+1;
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++)if(mp[i][j]>'0')p[i][j]=1;
}
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(p[i][j]){
			int id=GetID(i,j);
			AddEdge(id,r*c+id,mp[i][j]-'0');
			//bfs_add(i,j);
		}
	}
}
Build();
//printf("S:%d T:%d\n",S,T);
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(mp[i][j]=='L')AddEdge(S,GetID(i,j),1),rex++;
	}
}
printf("%d\n",rex-Dinic());
return 0;
}