jzoj5057 炮塔 网络流
2017-04-14 10:02:43         来源：Chunkit Lau’s blog

jzoj5057 炮塔 网络流 ：A君正在玩一款战略游戏，游戏中的规则是这样的：给定一个n*m的地图，地图上每一个位置要么是空地，要么是炮塔，要么有若干数量的敌人。现在A君要操控炮塔攻击这些敌人。

```#include
#include
#include
#include
#include
#define LD double
#define LL long long
#define ULL unsigned long long
#define min(a,b) ((ab)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=5*1e3+9,mm=1e5+9,inf=1e9;
int n,m,ans,gra=1,a[60][60],begin[mn],vis[mn],dis[mn],size[mm],next[mm],to[mm],
w[6][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};
int num(int x,int y,int z){
return ((x-1)*m+y)*2-z;
}
void insert2(int u,int v,int w){
to[++gra]=v;
size[gra]=w;
next[gra]=begin[u];
begin[u]=gra;
}
void insert(int u,int v,int w){
insert2(u,v,w);
insert2(v,u,0);
}
int updis(){
int tmp=inf;
fo(i,0,n*m*2+1)if(vis[i])fr(j,i)if(size[j]&&(!vis[to[j]]))
tmp=min(tmp,dis[to[j]]+1-dis[i]);
if(tmp==inf)return 0;
fo(i,0,n*m*2+1)if(vis[i])dis[i]+=tmp;
return 1;
}
vis[now]=1;
if(now==tar){
ans-=nsize;
return nsize;
}
fr(i,now)if((!vis[to[i]])&&size[i]&&(dis[now]==dis[to[i]]+1)){
if(tmp){
size[i]-=tmp;size[i^1]+=tmp;
return tmp;
}
}
return 0;
}
int main(){
//freopen("tower.in","r",stdin);
//freopen("tower.out","w",stdout);
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,n)fo(j,1,m)scanf("%d",&a[i][j]),insert(num(i,j,0),num(i,j,1),inf);
fo(i,1,n)fo(j,1,m)if(a[i][j]<0){
int mx=0;
fo(k,1,n){
int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))mx=max(mx,a[ii][jj]);
else break;
}
ans+=mx;
if((a[i][j]==-1)||(a[i][j]==-2)){
insert(0,num(i,j,0),mx);
fo(k,1,n){
int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))
insert(num(ii-w[-a[i][j]][0],jj-w[-a[i][j]][1],0),num(ii,jj,0),
min(mx,mx-a[ii-w[-a[i][j]][0]][jj-w[-a[i][j]][1]]));
else break;
}
}else if((a[i][j]==-3)||(a[i][j]==-4)){
insert(num(i,j,1),n*m*2+1,mx);
fo(k,1,n){
int ii=i+k*w[-a[i][j]][0],jj=j+k*w[-a[i][j]][1];
if((1<=ii)&&(ii<=n)&&(1<=jj)&&(jj<=m))
insert(num(ii,jj,1),num(ii-w[-a[i][j]][0],jj-w[-a[i][j]][1],1),
min(mx,mx-a[ii-w[-a[i][j]][0]][jj-w[-a[i][j]][1]]));
else break;
}
}
}
do{
fo(i,0,n*m*2+1)vis[i]=0;
fo(i,0,n*m*2+1)vis[i]=0;
}while(updis());
printf("%d",ans);
return 0;
}
```