1066: [SCOI2007]蜥蜴
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2582 Solved: 1272
[Submit][Status][Discuss]

Description
在一個(gè)r行c列的網(wǎng)格地圖中有一些高度不同的石柱，一些石柱上站著一些蜥蜴，你的任務(wù)是讓盡量多的蜥蜴逃到邊界外。 每行每列中相鄰石柱的距離為1，蜥蜴的跳躍距離是d，即蜥蜴可以跳到平面距離不超過(guò)d的任何一個(gè)石柱上。石柱都不穩(wěn)定，每次當(dāng)蜥蜴跳躍時(shí)，所離開(kāi)的石柱高度減1（如果仍然落在地圖內(nèi)部，則到達(dá)的石柱高度不變），如果該石柱原來(lái)高度為1，則蜥蜴離開(kāi)后消失。以后其他蜥蜴不能落腳。任何時(shí)刻不能有兩只蜥蜴在同一個(gè)石柱上。

Input
輸入第一行為三個(gè)整數(shù)r，c，d，即地圖的規(guī)模與最大跳躍距離。以下r行為石竹的初始狀態(tài)，0表示沒(méi)有石柱，1~3表示石柱的初始高度。以下r行為蜥蜴位置，“L”表示蜥蜴，“.”表示沒(méi)有蜥蜴。

Output
輸出僅一行，包含一個(gè)整數(shù)，即無(wú)法逃離的蜥蜴總數(shù)的最小值。

Sample Input
5 8 2
00000000
02000000
00321100
02000000
00000000
……..
……..
..LLLL..
……..
……..

Sample Output
1

HINT
100%的數(shù)據(jù)滿足：1<=r, c<=20, 1<=d<=4

Source
Pku 2711 Leapin’ Lizards

這道題啊，我想啊。。（模仿自謝老板） 一眼就看出是網(wǎng)絡(luò)流了，不過(guò)需要建圖，一般網(wǎng)絡(luò)流題目難點(diǎn)就在建圖上，所以在建圖上費(fèi)了心 建立超級(jí)源，與各初始有蜥蜴的柱子連邊，邊權(quán)為１ 建立超級(jí)匯，找可以跳出去的柱子與之連邊，邊權(quán)為ＩＮＦ 拆點(diǎn)：將每個(gè)柱子拆成兩個(gè)點(diǎn)（入點(diǎn)出點(diǎn)）入點(diǎn)到出點(diǎn)邊權(quán)為柱子高度 暴力將能夠互相跳到的點(diǎn)連邊（其中一點(diǎn)的出點(diǎn)連另一個(gè)點(diǎn)的入點(diǎn)），邊權(quán)為ＩＮＦ Ｄｉｎｉｃ一遍得到最多能跳出的蜥蜴數(shù)，總數(shù)減掉即可。。。

媽媽我再也不會(huì)把數(shù)組開(kāi)小了Ｏ（≧口≦）Ｏ

ＣＯＤＥ：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int r,c,d; int q[200000],h,t; int dis[2000]; struct data{int to,next,v; }edge[500001]; int cnt=1,head[2000]={0}; int n; int zh[25][25]={0};// 記錄柱子高度 int xys[25][25]={0};//蜥蜴數(shù) int bh[25][25]={0}; //編號(hào)（建圖用） int tot=0;//總蜥蜴數(shù) void add(int u,int v,int w) {cnt++;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].to=v;edge[cnt].v=w; }void init() {scanf("%d%d%d",&r,&c,&d);for (int i=1; i<=r; i++){char x[30];scanf("%s",&x);for (int j=1; j<=c; j++)zh[i][j]=x[j-1]-48;}for (int i=1; i<=r; i++){char x[30];scanf("%s",&x);for (int j=1; j<=c; j++)if (x[j-1]=='L'){tot++;xys[i][j]=1;}} }//讀入 void make()//超級(jí)源點(diǎn)為1，超級(jí)匯為n（最后的num） {int num=2;for (int i=1; i<=r; i++)for (int j=1; j<=c; j++){if (zh[i][j]>0){bh[i][j]=num;//bh【】記錄這個(gè)柱子的入點(diǎn)的編號(hào)（出點(diǎn)編號(hào)為入點(diǎn)編號(hào)+1） add(num,num+1,zh[i][j]);add(num+1,num,0);num+=2;}}//拆點(diǎn) for (int i=1; i<=r; i++)for (int j=1; j<=c; j++){if (xys[i][j]>0){add(1,bh[i][j],1);add(bh[i][j],1,0);}}//把初始有蜥蜴的與超級(jí)源連邊 for (int i=1; i<=r; i++)for (int j=1; j<=c; j++){if (zh[i][j]>0){for (int a=max(1,i-d); a<=min(r,i+d); a++)for (int b=max(1,j-d); b<=min(c,j+d); b++){if (zh[a][b]>0 && (a!=i || b!=j))if ((a-i)*(a-i)+(b-j)*(b-j)<=d*d){add(bh[i][j]+1,bh[a][b],0x7fffffff);add(bh[a][b],bh[i][j]+1,0);}} }}//暴力把能調(diào)到的兩個(gè)柱子連邊 for (int i=1; i<=r; i++)for (int j=1; j<=c; j++)if (zh[i][j]>0 && (i-d<=0 || i+d>r || j-d<=0 || j+d>c)){add(bh[i][j]+1,num,0x7fffffff);add(num,bh[i][j]+1,0);}//把能跳出去的柱子與超級(jí)匯連邊 n=num; }//建圖 bool bfs() {memset(dis,-1,sizeof(dis));q[1]=1;dis[1]=1;h=0; t=1;while (h<t){int j=q[++h],i=head[j];while (i){if (dis[edge[i].to]<0 && edge[i].v>0){dis[edge[i].to]=dis[j]+1;q[++t]=edge[i].to;}i=edge[i].next;}}if (dis[n]>0)return true;elsereturn false; }int dfs(int loc,int low) {int ans=0;if (loc==n) return low;int i=head[loc];while (i){if (edge[i].v>0 && dis[edge[i].to]==dis[loc]+1 && (ans=dfs(edge[i].to,min(low,edge[i].v)))){edge[i].v-=ans;edge[i^1].v+=ans;return ans;}i=edge[i].next;}return 0; }int main() {init();make();int ans=0;while (bfs()){int now;while ((now=dfs(1,0x7fffffff)))ans+=now;}printf("%d",tot-ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5346235.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ-1066 蜥蜴 最大流+拆点+超级源超级汇的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。