首页 > 代码库 > 【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..
........
........

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 #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]蜥蜴 (网络流)