[BZOJ4657]炮塔

• 这道题学长说比切糕简单，但是自我感觉，切糕就是个套路吧。这个建图有些恶心啊，并且需要思路转化。（其实是我思路江化太严重了）。
• 我们再描述一下问题，某个位置有一个炮塔，这个炮塔有一个方向。在这个方向上的所有点它可以任意选一个杀掉里面的敌人，但是每个炮塔攻击所覆盖的路径两两不能相交。求最大值。
• 我们上回写切糕的时候，见过了这类题目。选了某一个点之后，另一个相邻点的选择会受到限制。我们可以通过在网络上连边完成限制。
• 考虑把方向在上下的点作为竖点，方向在左右的点作为横点。建立源点S，向每个横点的炮塔连容量为inf的边，建立汇点T，每个竖点的炮塔向T连容量为inf的边。横点的每个炮塔，向他所攻击的方向，相邻点连边，容量先不管。竖点同理，不过反向建边：
  • 考虑为什么反向建边？假如我们割掉一条边代表选择了这个点，那么我们把竖点反向建边以后，如果两个炮塔攻击路径有交点，把这个横点的交点向竖点的交点连完边，就完成了对条件的限制（不懂的画一个图看看）。
• 但是如果我们直接把点权作为边权，求最小割，这样是不对的。
• 最小割求的是最小代价，而本题要求最大价值。我们可以让边权为一个差值啊！差值是当前选的点与这个炮塔能打到的最大值的差值，这样的话我们求一个最小割，也就是选了和最大值差值最小的，并且符合条件的，那么答案就是最大值减去最小割。

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=500*50*5;
const int inf=1e9;
int n,m,S,T,tot=1,a[60][60],ver[N],Next[N],lin[N],edge[N],d[N],num1,num2;
int ans,flow,maxflow;
struct node{int x,y,siz;
}he[N],le[N];
int read(){int k;scanf("%d",&k);return k;}
int cal(int k,int i,int j){return k*n*m+(i-1)*m+j;}
void add(int x,int y,int z){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;
}
void init(){n=read(),m=read();for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){a[i][j]=read();if(a[i][j]==-1||a[i][j]==-2) le[++num2].x=i,le[num2].y=j;if(a[i][j]==-3||a[i][j]==-4) he[++num1].x=i,he[num1].y=j;}
}
void build(){S=0,T=2*n*m+1;for(int i=1;i<=num1;++i){int tx=he[i].x,ty=he[i].y;int temp=0;if(a[tx][ty]==-3){for(int j=ty-1;j>0;--j) if(temp<a[tx][j]) temp=a[tx][j];for(int j=ty;j>1;--j) add(cal(0,tx,j),cal(0,tx,j-1),temp-max(0,a[tx][j]));}else{for(int j=ty+1;j<=m;++j) if(temp<a[tx][j]) temp=a[tx][j];for(int j=ty;j<m;++j) add(cal(0,tx,j),cal(0,tx,j+1),temp-max(0,a[tx][j]));}ans+=temp;add(S,cal(0,tx,ty),inf);}for(int i=1;i<=num2;++i){int tx=le[i].x,ty=le[i].y;int temp=0;if(a[tx][ty]==-1){for(int j=tx-1;j>0;--j) if(temp<a[j][ty]) temp=a[j][ty];for(int j=tx;j>1;--j) add(cal(1,j-1,ty),cal(1,j,ty),temp-max(0,a[j][ty]));}else{for(int j=tx+1;j<=n;++j) if(temp<a[j][ty]) temp=a[j][ty];for(int j=tx;j<n;++j) add(cal(1,j+1,ty),cal(1,j,ty),temp-max(0,a[j][ty]));}ans+=temp;add(cal(1,tx,ty),T,inf);}for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) add(cal(0,i,j),cal(1,i,j),inf);
}
bool bfs(){queue<int>q;memset(d,0,sizeof(d));d[S]=1;q.push(S);while(q.size()){int x=q.front();q.pop();for(int i=lin[x];i;i=Next[i]){int y=ver[i];if(edge[i]&&!d[y]){d[y]=d[x]+1;q.push(y);if(y==T) return 1;}}}return 0;
}
int dinic(int x,int flow){int rest=flow;if(x==T) return flow;for(int i=lin[x];i&&rest;i=Next[i]){int y=ver[i];if(edge[i]&&d[y]==d[x]+1){int k=dinic(y,min(edge[i],rest));if(!k) d[y]=0;rest-=k;edge[i]-=k;edge[i^1]+=k;if(!rest) return flow-rest;}}return flow-rest;
}
void work(){while(bfs()){while(flow=dinic(S,inf)) maxflow+=flow;}//cout<printf("%d\n",ans-maxflow);
}
int main(){//freopen("cti.in","r",stdin);
//	freopen("cti.out","w",stdout);init();build();//for(int i=2;i<=tot;i+=2) cout<work();return 0;
}