首页 > 代码库 > 【bzoj】 1066: [SCOI2007]蜥蜴 (网络流)
【bzoj】 1066: [SCOI2007]蜥蜴 (网络流)
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..
........
........
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
Sample Output
1
HINT
100%的数据满足:1<=r, c<=20, 1<=d<=4
Source
对于每个石柱,我们把它拆成2个点,称为入点和出点,入点和出点连一条边,容量为高度,如果A石柱能跳到B石柱,就把出点A和入点B连一条边,容量为无限,这条边模拟的是跳的过程。如果该石柱能跳出去,就在该石柱出点和汇点T连一条边,容量无限。这条边模拟跳出去的过程。 如果该石柱有蜥蜴,在源点S和该石柱入点连一条边,容量为1.
这样的话,每个有蜥蜴的石柱上都有一只蜥蜴,如果该蜥蜴想从该石柱跳开,必定要先从该石柱入点跑到该石柱出点,这样会消耗1的容量,然后跳出去后,跳到另一石柱时,想再跳的话,又会消耗那个石柱的容量 ,直到跳到汇点T,贡献了1的流量。所以这幅图的最大流表示的就是能逃脱的蜥蜴数量,输出答案时减一下就行了。
这样的话,每个有蜥蜴的石柱上都有一只蜥蜴,如果该蜥蜴想从该石柱跳开,必定要先从该石柱入点跑到该石柱出点,这样会消耗1的容量,然后跳出去后,跳到另一石柱时,想再跳的话,又会消耗那个石柱的容量 ,直到跳到汇点T,贡献了1的流量。所以这幅图的最大流表示的就是能逃脱的蜥蜴数量,输出答案时减一下就行了。
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #define MAXN 1000010 6 #define NM 400 7 8 const int INF=0x7fffffff; 9 10 using namespace std; 11 12 int n,m,d,src,decc,ans; 13 14 int map[202][202],mark[202][202],depth[MAXN],cur[MAXN]; 15 16 char s[202],ms[202][202]; 17 18 queue<int> q; 19 20 struct node { 21 int to; 22 int next; 23 int val; 24 }; 25 node e[MAXN]; 26 27 int head[MAXN],tot; 28 29 inline void add(int x,int y,int val) { 30 e[++tot].to=y; 31 e[tot].val=val; 32 e[tot].next=head[x]; 33 head[x]=tot; 34 e[++tot].to=x; 35 e[tot].val=0; 36 e[tot].next=head[y]; 37 head[y]=tot; 38 } 39 40 inline bool bfs() { 41 for(int i=0;i<=decc;i++) cur[i]=head[i],depth[i]=-1; 42 while(!q.empty()) q.pop(); 43 q.push(src);depth[src]=0; 44 while(!q.empty()) { 45 int u=q.front(); 46 q.pop(); 47 for(int i=head[u];i;i=e[i].next) { 48 int to=e[i].to; 49 if(e[i].val&&depth[to]==-1) { 50 q.push(to); 51 depth[to]=depth[u]+1; 52 if(to==decc) return true; 53 } 54 } 55 } 56 return false; 57 } 58 59 inline int dinic(int now,int flow) { 60 if(now==decc) return flow; 61 int rest=0,delat; 62 for(int & i=cur[now];i;i=e[i].next) { 63 int to=e[i].to; 64 if(e[i].val&&depth[to]==depth[now]+1) { 65 delat=dinic(to,min(e[i].val,flow-rest)); 66 if(delat) { 67 e[i].val-=delat; 68 e[i^1].val+=delat; 69 rest+=delat; 70 if(rest==flow) break; 71 } 72 } 73 } 74 if(rest!=flow) depth[now]=-1; 75 return rest; 76 } 77 78 int main() { 79 scanf("%d%d%d",&n,&m,&d); 80 decc=2*NM+1; 81 for(int i=1;i<=n;i++) { 82 scanf("%s",s); 83 for(int j=0;j<m;j++) { 84 map[i][j+1]=s[j]-48; 85 } 86 } 87 for(int i=1;i<=n;i++) 88 for(int j=1;j<=m;j++) 89 tot++,mark[i][j]=tot; 90 tot=1; 91 for(int i=1;i<=n;i++) { 92 scanf("%s",s); 93 for(int j=0;j<m;j++) 94 if(s[j]==‘L‘) 95 ans++, 96 add(src,mark[i][j+1],1); 97 } 98 for(int i=1;i<=n;i++) 99 for(int j=1;j<=m;j++) {100 if(map[i][j]) {101 add(mark[i][j],mark[i][j]+NM,map[i][j]);102 for(int k=i-d;k<=i+d;k++)103 for(int l=j-d;l<=j+d;l++) {104 if((i!=k||j!=l)&&map[k][l]&&(((k-i)*(k-i)+(l-j)*(l-j))<=d*d)) {105 add(mark[i][j]+NM,mark[k][l],INF);106 }107 }108 }109 }110 for(int i=1;i<=d;i++) //可以跳到外界的点 111 for(int j=d+1;j<=n-d;j++) {112 add(mark[j][i]+NM,decc,INF);113 add(mark[j][m-i+1]+NM,decc,INF);114 }115 for(int i=1;i<=d;i++)116 for(int j=1;j<=m;j++) {117 add(mark[i][j]+NM,decc,INF);118 add(mark[n-i+1][j]+NM,decc,INF);119 }120 while(bfs()) ans-=dinic(src,INF);121 printf("%d\n",ans);122 return 0;123 }
【bzoj】 1066: [SCOI2007]蜥蜴 (网络流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。