1066: [SCOI2007]蜥蜴
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2947 Solved: 1471
[Submit][Status][Discuss]
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
![BZOJ 1066 POJ 2711 [SCOI2007]蜥蜴](https://image.shishitao.com:8440/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTYwNTE4MTgxMDQwMzU3P3dhdGVybWFyay8yL3RleHQvYUhSMGNEb3ZMMkpzYjJjdVkzTmtiaTV1WlhRdi9mb250LzVhNkw1TDJUL2ZvbnRzaXplLzQwMC9maWxsL0kwSkJRa0ZDTUE9PS9kaXNzb2x2ZS83MC9ncmF2aXR5L0NlbnRlcg%3D%3D.jpg?w=700&webp=1 "BZOJ 1066 POJ 2711 [SCOI2007]蜥蜴")
从隔壁Orion_Rigel博客搬了张思路图过来（我是盗图王）
感觉代码规模差不多，为何为TLE呢？
先放TLE的代码，以后AC了再更新
————UPD2017.5
一拖就拖了一年的节奏？
其实只要换成邻接表就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int mxn=;
struct edge{
int v,nxt,f;
}e[mxn*mxn];
int hd[mxn],mct=;
void add_edge(int u,int v,int f){
e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return;
}
void insert(int u,int v,int f){
if(!v)return;
// printf("%d to %d : %d\n",u,v,f);
add_edge(u,v,f); add_edge(v,u,);
return;
}
int n,m,D,S,T;
int d[mxn];
bool BFS(){
queue<int>q;
memset(d,,sizeof d);
d[S]=;q.push(S);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(!d[v] && e[i].f){
// printf("%d to %d :%d\n",u,v,e[i].f);
d[v]=d[u]+;
q.push(v);
}
}
}
return d[T];
}
int DFS(int u,int lim){
if(u==T)return lim;
int f=,tmp;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(e[i].f && d[v]==d[u]+ && (tmp=DFS(e[i].v,min(lim,e[i].f)))){
e[i].f -=tmp;
e[i^].f+=tmp;
f+=tmp;
lim -=tmp;
if(!lim)return f;
}
}
d[u]=;
return f;
}
int Dinic(){
int res=;
while(BFS())res+=DFS(S,INF);//,printf("res:%d\n",res);
return res;
}
int id[][],sz=,lct=;
int mp[][];
void ADD(int x,int y,int out){
bool flag=;
for(int i=x-D;i<=x+D;i++){
for(int j=y-D;j<=y+D;j++){
if(i==x && j==y)continue;
if( (i-x)*(i-x)+(j-y)*(j-y)<=D*D ){
if(i< || i>n || j< || j>m){if(!flag)insert(out,T,INF),flag=;}
else insert(out,id[i][j],INF);
}
}
}
return;
}
void Build(){
T=sz+sz+lct+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
int out=id[i][j]+lct+sz;
if(mp[i][j]){
// printf("[%d %d ]%d\n",i,j,mp[i][j]);
insert(id[i][j],out,mp[i][j]);
ADD(i,j,out);
}
}
return;
}
char sc[];
int main(){
// freopen("in.txt","r",stdin);
int i,j;
scanf("%d%d%d",&n,&m,&D);
for(i=;i<=n;i++){
scanf("%s",sc+);
for(j=;j<=m;j++){
mp[i][j]=sc[j]-'';
if(mp[i][j])id[i][j]=++sz;
}
}
S=;
for(i=;i<=n;i++){
scanf("%s",sc+);
for(j=;j<=m;j++){
if(sc[j]=='L'){
++lct;
insert(S,lct+sz,);
insert(lct+sz,id[i][j],);
}
}
}
Build();
int ans=Dinic();
// printf("%d\n",ans);
/* for(i=hd[2];i;i=e[i].nxt){
int v=e[i].v;
printf("%d %d : %d\n",2,v,e[i].f);
}*/
printf("%d\n",lct-ans);
return ;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int INF=0x6ffffff;
struct NODE{
int w;//容量(在此题中为石柱高度)
int f;//流量
}e[][];//邻接矩阵流量边
int r,c;
int s,t;
int dis;//跳跃距离
int mp[][],//坐标为[x][y]的点是否为结点，是的话记录节点号
ht[][];//高度
int cnode=,clizard=;//结点数 蜥蜴数
//
int add_eg(int u,int v,int h){
e[u][v].w=h;
}
int pd(int x1,int y1,int x2,int y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=dis*dis;
}
//
int q[],d[];
bool flag[];
int BFS(){
int hd=,tl=;
int u,v;
memset(flag,,sizeof(flag));
q[hd]=s;d[s]=;flag[s]=;
while(hd<=tl){
u=q[hd];
for(v=;v<=t;v++){
if(!flag[v] && e[u][v].w>e[u][v].f){
flag[v]=;
d[v]=d[u]+;
q[++tl]=v;
}
if(flag[t])return ;
}
hd++;
}
return ; }
int DFS(int v,int low){
int i; int flow;
if(v==t)return low;
for(i=;i<=t;i++){
if(e[v][i].w>e[v][i].f && d[i]==d[v]+){
if(flow=DFS(i,min(low,e[v][i].w-e[v][i].f))){
e[v][i].f+=flow;
e[i][v].f=-e[v][i].f;
return flow;
}
}
}
return ;
}
int dinic(){
int ans=;
while(BFS()){
int flow;
while(flow=DFS(s,INF)){
ans+=flow;
}
}
return ans;
}
int main(){
scanf("%d%d%d",&r,&c,&dis);
int i,j;
char ch[];
for(i=;i<=r;i++){//读石柱图
scanf("%s",ch);
for(j=;j<c;j++){
ht[i][j+]=ch[j]-'';
if(ht[i][j+]>)mp[i][j+]=++cnode;
}
}
s=;t=cnode*+;
for(i=;i<=r;i++){//读蜥蜴图
scanf("%s",ch);
for(j=;j<c;j++){
if(ch[j]=='L'){
add_eg(s,mp[i][j+],);
clizard++;
}
}
}
for(i=;i<=r;i++){
for(j=;j<=c;j++){ if(mp[i][j]){ //建石柱自身到自身镜像的容量为石柱高度的边
add_eg(mp[i][j],mp[i][j]+cnode,ht[i][j]); if(i<=dis || i+dis>r || j<=dis || j+dis>c)
add_eg(mp[i][j]+cnode,t,INF);//建出区域的边
int a,b;
for(a=max(i-dis,);a<=min(i+dis,r);a++)
for(b=max(j-dis,);b<=min(j+dis,c);b++){
if(i!=a || b!=j)
if(pd(i,j,a,b)) add_eg(mp[i][j]+cnode,mp[a][b],INF);//建石柱之间的边
}
}
}
}
int ans=dinic();
// printf("%d %d",clizard,ans);
printf("%d\n",clizard-ans);
return ;
}
TLE