1066: [SCOI2007]蜥蜴 Time Limit: 1 Sec Memory Limit: 162 MB Description 在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃 到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石 柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不 变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个 石柱上。 Input 输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱 ，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。 Output 输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。 Sample Input 5 8 2 00000000 02000000 00321100 02000000 00000000 …….. …….. ..LLLL.. …….. …….. Sample Output 1 HINT 100%的数据满足：1<=r, c<=20, 1<=d<=4 Source Pku 2711 Leapin’ Lizards
/*最大流.把每个柱子拆成两个点.然后由原点向有蜥蜴的点连一条流量为1的边表示这儿有蜥蜴.然后在高度不为0的点拆点后的点之间建一条流量为石柱高度的边表示可以蹦的次数.然后在有蜥蜴的两点分别拆点前后的点之间建一条流量为INF的边表示蜥蜴在任意时刻都可以从这儿蹦到那儿.然后在可以蹦出去的点处与汇点建一条流量为INF的边表示在这儿永远可以蹦出去.只会感性的认识hhh,毕竟弱啊orz. */#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<queue>#define MAXN 51#define MAXM 320000#define INF 1e6using namespace std;int n,m,d,tot,ans,cut=1,dis[MAXN*MAXN],head[MAXN*MAXN];struct data{int v,next,c;}e[MAXM*2];char g[MAXN][MAXN],s[MAXN][MAXN];queue<int>q;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void add(int u,int v,int x){ e[++cut].v=v;e[cut].c=x;e[cut].next=head[u];head[u]=cut; e[++cut].v=u;e[cut].c=0;e[cut].next=head[v];head[v]=cut;}bool check(int i,int j,int k,int l){ return sqrt((i-k)*(i-k)+(j-l)*(j-l))<=(double)d;}int judge(int x,int y){ if (x<=d||n-x<d||y<=d||m-y<d) return 1; return 0;}void slove(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!s[i][j]) continue; for(int k=1;k<=n;k++) for(int l=1;l<=m;l++) { if(!s[k][l]) continue; if(i==k&&j==l) continue; if(check(i,j,k,l)) { add((i-1)*m+j+n*m,(k-1)*m+l,INF); add((k-1)*m+l+n*m,(i-1)*m+j,INF); } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(judge(i,j)) add((i-1)*m+j+n*m,n*m*2+1,INF);}bool bfs(){ memset(dis,-1,sizeof dis); q.push(0);dis[0]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]==-1&&e[i].c) { dis[v]=dis[u]+1; q.push(v); } } } return dis[n*m*2+1]!=-1;}int dfs(int u,int y){ if(u==n*m*2+1) return y; int rest=0; for(int i=head[u];i&&rest<y;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1&&e[i].c) { int x=dfs(v,min(e[i].c,y-rest)); rest+=x; e[i].c-=x; e[i^1].c+=x; } } if(!rest) dis[u]=-1; return rest;}void dinic(int s,int t){ while(bfs()) ans+=dfs(0,INF); return ;}int main(){ n=read(),m=read(),d=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>s[i][j];s[i][j]-='0'; if(s[i][j]) add((i-1)*m+j,(i-1)*m+j+n*m,s[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>g[i][j]; if(g[i][j]=='L') add(0,(i-1)*m+j,1),tot++; } slove(); dinic(0,n*m*2+1); PRintf("%d",tot-ans); return 0;}新闻热点
疑难解答
