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);新聞熱點
疑難解答
