题目链接：https://cn.vjudge.net/contest/281959#problem/E
题目大意：中文题目
具体思路：首先，有矛盾的时候就是两个导弹的运动轨迹会相交的时候，那么我们可以按照这样的思路，在每个导弹不想交的前提下，使得总的消灭数最大。然后我们就可以了按照会相交的方式建图，求出最小割，然后再用总和减去最小割，就能得出最大的消灭量了。
建图的时候，首先横点向竖点连边，权值是inf。每一个炮弹记录他能打到的最大的消灭数，然后对于横着的炮台，从当前的炮台出发到最大的消灭数所在的位置，每一步的权值就是max-当前这个点的权值，最终求的答案的时候，所有炮台的最大值的总和-最小割就是最大消灭数了。
AC代码：
#include<iostream>
#include<stack>
#include<queue>
#include<iomanip>
#include<stdio.h>
#include<cstring>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
# define ll long long
const int maxn = +;
const int inf = 0x3f3f3f3f;
int prev[maxn];
int head[maxn];
int dx[]= {-,,,};
int dy[]= {,,-,};
int A[][],B[][],w[][];
struct node
{
int to;
int flow;
int nex;
} edge[maxn];
int num,st,ed;
void init()
{
memset(head,-,sizeof(head));
num=;
}
void addedge(int fr,int to,int flow)
{
edge[num].to=to;
edge[num].flow=flow;
edge[num].nex=head[fr];
head[fr]=num++;
edge[num].to=fr;
edge[num].flow=;
edge[num].nex=head[to];
head[to]=num++;
}
bool bfs()
{
memset(prev,-,sizeof(prev));
prev[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int top=q.front();
q.pop();
for(int i=head[top]; i!=-; i=edge[i].nex)
{
int temp=edge[i].to;
if(prev[temp]==-&&edge[i].flow>)
{
prev[temp]=prev[top]+;
q.push(temp);
}
}
}
return prev[ed]!=-;
}
int dfs(int u,int flow)
{
if(u==ed)
return flow;
int res=;
for(int i=head[u]; i!=-; i=edge[i].nex)
{
int t=edge[i].to;
if(prev[t]==(prev[u]+)&&edge[i].flow>)
{
int temp=dfs(t,min(flow,edge[i].flow));
edge[i].flow-=temp;
edge[i^].flow+=temp;
res+=temp;
flow-=temp;
if(flow==)
break;
}
}
if(res==)
prev[u]=-;
return res;
}
int n,m;
int dinic()
{
int ans=;
while(bfs())
{
ans+=dfs(st,inf);
}
return ans;
}
int cal()
{
int ans=,x,y;
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
{
if (w[i][j] >= ) continue;
int dir = -(w[i][j] + ),Max = w[i][j] = ;
for (int x = i + dx[dir],y = j + dy[dir]; ;)
{
if (x < || x > n || y < || y > m) break;
Max = max(Max,w[x][y]); x += dx[dir]; y += dy[dir];
}
ans += Max;
if (dir <= )
{
addedge(st,A[i][j],inf);
for (int x = i + dx[dir],y = j + dy[dir]; ;)
{
if (x < || x > n || y < || y > m) break;
addedge(A[x - dx[dir]][y - dy[dir]],A[x][y],Max - w[x - dx[dir]][y - dy[dir]]);
x += dx[dir]; y += dy[dir];
}
}
else
{
addedge(B[i][j],ed,inf);
for (int x = i + dx[dir],y = j + dy[dir]; ;)
{
if (x < || x > n || y < || y > m) break;
addedge(B[x][y],B[x - dx[dir]][y - dy[dir]],Max - w[x - dx[dir]][y - dy[dir]]);
x += dx[dir]; y += dy[dir];
}
}
}
return ans;
}
int main()
{
init();
int tot=;
scanf("%d %d",&n,&m);
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
A[i][j]=++tot,B[i][j]=++tot;
scanf("%d",&w[i][j]);
addedge(A[i][j],B[i][j],inf);
}
}
st=++tot,ed=++tot;
int sum=cal();
int ans=dinic();
// cout<<sum<<" "<<ans<<endl;
printf("%d\n",sum-ans);
return ;
}