题目链接：传送门
题目大意：给你 n，m n:有几行图，m是一个人最多跳m个曼哈顿距离。
给你两张图，第一张图数字为0表示没有柱子，否则有柱子且只能跳出去 x 次（x为当前字符代表的数字）
第二张图 '.'表示没人，'L'表示当前位置有一个人，问通过柱子之间跳跃最后最少有多少人不能逃出去。
逃出去只能是柱子与边界的最小曼哈顿距离小于等于 m。
题目思路：拆点网络流
首先虚拟源汇点 S，T
其实这道题构图建模不难想，既然某个柱子只能跳 x 次，那就把它拆为两点，连边容量为 x，这样保证合法性。
相互之间可达的柱子连边容量 inf，因为柱子已经拆点来保证合法，所以柱子间初始化不用受限制。
可与外界相通的柱子与 T 连边容量 inf，刚开始有人的柱子与 S 连边容量为 1。
然后ISAP跑网络流即可。
此题坑点：输出时注意单复数输出的不同
久违的1A
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 2000000 #define maxn 500005 typedef pair<int,int> PII; typedef long long LL; map<PII,int>M; ///map来记录点 int n,m,ccnt,S,T,len,peo,ans; int head[1000],hcnt,d[1000],pre[1000],gap[1000],cur[1000]; char pic[50][50]; struct Crd{int x,y,v;}co[1000]; struct Node{int to,nxt,f;Node(){}Node(int a,int b,int c):to(a),nxt(b),f(c){}}node[N]; bool judge(int x,int y){ ///曼哈顿距离判断 int temp=abs(co[x].x-co[y].x); temp+=abs(co[x].y-co[y].y); return temp<=m; } inline void add(int x,int y,int f){ node[hcnt]=Node(y,head[x],f);head[x]=hcnt++; node[hcnt]=Node(x,head[y],0);head[y]=hcnt++; } void ISAP(int S,int T,int n){ ans=0; int aug=inf,i,flag; int u,e,dis; mst(gap,0);mst(d,0); for(i=0;i<=n;++i)cur[i]=head[i]; u=pre[S]=S; while(d[S]<n){ flag=0; for(i=cur[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].f>0&&d[u]==d[e]+1){ flag=1; break; } } if(flag){ pre[e]=u; cur[u]=i; aug=min(aug,node[i].f); u=e; if(u==T){ while(u!=S){ u=pre[u]; node[cur[u]].f-=aug; node[cur[u]^1].f+=aug; } u=S; ans+=aug; aug=inf; } } else{ if(--gap[d[u]]==0)break; dis=n; cur[u]=head[u]; for(int i=head[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].f>0&&d[e]+1<dis){ dis=d[e]+1; cur[u]=i; } } d[u]=dis; ++gap[dis]; if(u!=S)u=pre[u]; } } } int main(){ int i,j,group,Case=0; scanf("%d",&group); while(group--){ M.clear(); len=hcnt=0;ccnt=0; mst(head,-1); scanf("%d%d",&n,&m); gets(pic[1]); for(i=1;i<=n;++i){ gets(pic[i]+1); if(!len)len=strlen(pic[i]+1); for(j=1;j<=len;++j){ if(pic[i][j]>'0'){ co[++ccnt].x=i; ///ccnt是点的个数 co[ccnt].y=j; co[ccnt].v=pic[i][j]-'0'; M[make_pair(i,j)]=ccnt; } } } S=0;T=ccnt*2+1; for(i=1;i<=ccnt;++i){ add(i,i+ccnt,co[i].v); ///柱子拆点连边 if(co[i].x<=m||(n-co[i].x+1)<=m||co[i].y<=m||(len-co[i].y+1)<=m) add(i+ccnt,T,inf); ///与外界相通的柱子 for(j=1;j<i;++j){ if(judge(i,j)){ add(i+ccnt,j,inf); ///相互可达的柱子 add(j+ccnt,i,inf); } } } peo=0; ///一共多少人 for(i=1;i<=n;++i){ gets(pic[i]+1); for(j=1;j<=len;++j){ if(pic[i][j]=='L'){ ++peo; int tt=M[make_pair(i,j)]; add(S,tt,1); } } } ISAP(S,T,T+1); ans=peo-ans; printf("Case #%d: ",++Case); if(!ans)printf("no lizard was left behind. "); else if(ans==1)printf("1 lizard was left behind. "); else printf("%d lizards were left behind. ",ans); } return 0; }