BZOJ4657 : tower

显然只有横向和纵向的两个炮塔才有可能冲突。

考虑最小割，将每个炮塔所有能攻击到的位置建点，相邻之间连无穷的边，表示前缀和关系，即选了一个点，就必须要选所有比它近的点。

属于横向炮塔的点向$S$连边，容量为前缀最大值的差值；属于纵向炮塔的点向$T$连边，容量为前缀最大值的差值。

对于一个交点，则在两个点之间连无穷边，表示必须舍弃其中一个。

答案$=$总收益$-$最小割。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=126000,inf=~0U>>2;

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

struct E{int t,f;E*nxt,*pair;}*g[N],*d[N],pool[1000000],*cur=pool;

int n,m,i,j,a[55][55],b[55][55],cnt,S,T,h[N],gap[N],ans;

inline void add(int s,int t,int f){

  if(!f)return;

  if(f<inf)ans+=f;

  E*p=cur++;p->t=t;p->f=f;p->nxt=g[s];g[s]=p;

  p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p;

  g[s]->pair=g[t];g[t]->pair=g[s];

}

int sap(int v,int flow){

  if(v==T)return flow;

  int rec=0;

  for(E*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){

    int ret=sap(p->t,min(flow-rec,p->f));

    p->f-=ret;p->pair->f+=ret;d[v]=p;

    if((rec+=ret)==flow)return flow;

  }

  if(!(--gap[h[v]]))h[S]=T;

  gap[++h[v]]++;d[v]=g[v];

  return rec;

}

inline void tag(int x,int y,int k){

  int mx=0,pre=0,now;

  while(1){

    x+=dx[k],y+=dy[k];

    if(x<1||x>n||y<1||y>m)return;

    cnt++;

    if(pre){

      if(k<2)add(cnt,pre,inf);

      else add(pre,cnt,inf);

    }

    if(k<2)add(S,cnt,max(mx,a[x][y])-mx);else add(cnt,T,max(mx,a[x][y])-mx);

    mx=max(mx,a[x][y]);

    pre=cnt;

    if(b[x][y]){

      if(k<2)add(cnt,b[x][y],inf);

      else add(b[x][y],cnt,inf);

    }else b[x][y]=cnt;

  }

}

int main(){

  scanf("%d%d",&n,&m);

  S=n*m*max(n,m)+1;T=S+1;

  for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);

  for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]<0)tag(i,j,a[i][j]+4);

  for(gap[0]=T,i=1;i<=T;i++)d[i]=g[i];

  while(h[S]<T)ans-=sap(S,inf);

  return printf("%d",ans),0;

}