首页 > 代码库 > 【bzoj】 1066: [SCOI2007]蜥蜴 (网络流)

【bzoj】 1066: [SCOI2007]蜥蜴 (网络流)

2024-10-28 14:05:39   211人阅读

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


联系
我们