[SCOI2007] 蜥蜴
题目背景
07 四川省选
题目描述
在一个 r 行 c 列的网格地图中有一些高度不同的石柱, 一些石柱上站着一些蜥蜴, 你的任务是让尽量多的蜥蜴逃到边界外.
每行每列中相邻石柱的距离为 1, 蜥蜴的跳跃距离是 d, 即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上. 石柱都不稳定, 每次当蜥蜴跳跃时, 所离开的石柱高度减 1(如果仍然落在地图内部, 则到达的石柱高度不变), 如果该石柱原来高度为 1, 则蜥蜴离开后消失. 以后其他蜥蜴不能落脚. 任何时刻不能有两只蜥蜴在同一个石柱上.
输入输出格式
输入格式:
输入第一行为三个整数 r,c,d, 即地图的规模与最大跳跃距离. 以下 r 行为石柱的初始状态, 0 表示没有石柱, 1~3 表示石柱的初始高度. 以下 r 行为蜥蜴位置,"L" 表示蜥蜴,"." 表示没有蜥蜴.
输出格式:
输出仅一行, 包含一个整数, 即无法逃离的蜥蜴总数的最小值.
输入输出样例
输入样例 #1:
- 5 8 2
- 00000000
- 02000000
- 00321100
- 02000000
- 00000000
- ........
- ........
..LLLL..
- ........
- ........
输出样例 #1:
1
说明
100% 的数据满足:$1<=r, c<=20, 1<=d<=4$
Solution
看到题目中的柱子每经一次高度 - 1 马上想到网络流, 每根柱子的高度就是网络中一条边的容量
其实网络流的题目一般就是考建边, 建完以后套个最大流模板就行了
那么怎么建边呢?
建一个源点 S, 汇点 T(都是虚点)
考虑拆点, 我们把一个柱子拆成入点和出点, 把这两个点之间建一条容量为柱子高度 x 的边, 代表这棵柱子最多只能经过 x 次
对于能够到达地图外的点, 我们之间从它的出点向汇点建一条容量为 inf 的边
枚举两个柱子, 在地图上欧几里得距离小于最大跳跃距离的点之间建一条容量为 inf 的边
由源点向每个蜥蜴所在的点建一条容量为 1 的边, 代表这个点有一个蜥蜴
- Code
- #include<bits/stdc++.h>
- #define rg register
- #define il inline
- #define Min(a,b) (a)<(b)?(a):(b)
- #define Max(a,b) (a)>(b)?(a):(b)
- #define dis(a,b,x,y) ((x-a)*(x-a)+(y-b)*(y-b))
- using namespace std;
- const int N=100,M=1e6+10;
- const int inf=2e9;
- void in(int &ans) {
- ans=0; char i=getchar();
- while(i<'0' || i>'9') i=getchar();
- while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
- }
- int n,m,d,cur=1,ans;
- int S,T,NN,c1,c2,sum;
- char ch;
- int to[M<<1],nex[M<<1],head[M],cap[M<<1],lev[M],curr[M];
- int c[N][N],p[N][N];
- int l[M<<1],r[M<<1];
- struct node {
- int l,r;
- };
- vector<node>v;
- il void add(int a,int b,int c) {
- to[++cur]=b,nex[cur]=head[a];
- cap[cur]=c,head[a]=cur;
- }
- il void read() {
- NN=n*m; T=2*n*m+1;
- for(int i=1;i<=n;i++) {
- for(int j=1;j<=m;j++) {
- cin>>ch; p[i][j]=++c1;
- c[i][j]=ch-'0';
- if(c[i][j]) l[++c2]=i,r[c2]=j;
- }
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++) {
- cin>>ch; if(ch=='L') sum++,v.push_back((node){i,j});
- }
- }
- il void init() {
- for(int i=1;i<=c2;i++) {
- add(p[l[i]][r[i]],p[l[i]][r[i]]+NN,c[l[i]][r[i]]);
- add(p[l[i]][r[i]]+NN,p[l[i]][r[i]],0);
- if(l[i]<=d || r[i]<=d || l[i]+d>n || r[i]+d>m) {
- add(p[l[i]][r[i]]+NN,T,inf);
- add(T,p[l[i]][r[i]]+NN,0);
- }
- }
- for(int i=1;i<=c2;i++)
- for(int j=1;j<=c2;j++) {
- if(dis(l[i],r[i],l[j],r[j])<=d*d && i!=j) {
- add(p[l[i]][r[i]]+NN,p[l[j]][r[j]],inf);
- add(p[l[j]][r[j]],p[l[i]][r[i]]+NN,0);
- }
- }
- for(int i=0;i<sum;i++) {
- add(S,p[v[i].l][v[i].r],1);
- add(p[v[i].l][v[i].r],S,0);
- }
- }
- bool bfs(int s,int t) {
- queue<int>q; memset(lev,-1,sizeof(lev));
- q.push(s); lev[s]=0;
- while(!q.empty()) {
- int u=q.front(); q.pop();
- for(int i=head[u];i;i=nex[i]) {
- if(lev[to[i]]==-1 && cap[i]>0) {
- lev[to[i]]=lev[u]+1;
- q.push(to[i]);
- }
- }
- }
- return lev[t]!=-1;
- }
- int dfs(int s,int f,int t,int rest=0) {
- if(s==t) return f;
- for(int i=head[s];i;i=nex[i]) {
- if(lev[to[i]]==lev[s]+1 && cap[i]>0) {
- int r=dfs(to[i],Min(cap[i],f-rest),t);
- if(r>0) rest+=r,cap[i]-=r,cap[i^1]+=r;
- }
- }
- if(!rest) lev[s]=-1;
- return rest;
- }
- int main()
- {
- in(n),in(m),in(d);
- read(); init();
- while(bfs(S,T))
- while(int c=dfs(S,inf,T)) ans+=c;
- printf("%d\n",sum-ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2762871.html