根据 RHX 大佬的名言：「看到这种有奇怪限制，正常人做不出来的题，就可以考虑网络流。」
看起来像费用流，但是并布星（
注意到相交可以看做连通，于是可以往最小割的方向考虑。
建图的大体思想是横纵连的方向要相反，割一条边相当于打到某个位置。
具体可参见代码。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using namespace std;
const int N = 50;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = { 0, 0,-1, 1};
int n,m,s,t;
int a[N + 5][N + 5],ans;
namespace Dinic
{
const int N = 5002;
const int M = 1e5;
int n;
int to[(M << 1) + 5],val[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5],cur[N + 5],edge_tot;
inline int init()
{
memset(first,-1,sizeof first);
return 0;
}
int Init = init();
inline void add_edge(int u,int v,int w)
{
int &tot = edge_tot;
to[tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot++;
}
inline void add(int u,int v,int w)
{
add_edge(u,v,w),add_edge(v,u,0);
}
int head,tail,q[N + 5],dep[N + 5],vis[N + 5];
int bfs()
{
head = tail = 0;
memset(vis,0,sizeof vis);
memset(dep,0x3f,sizeof dep);
dep[s] = 0,vis[s] = 1,q[++tail] = s;
while(head < tail)
{
int p = q[++head];
vis[p] = 0;
for(register int i = first[p];~i;i = pre[i])
if(val[i] && dep[to[i]] > dep[p] + 1)
{
dep[to[i]] = dep[p] + 1;
if(!vis[to[i]])
vis[to[i]] = 1,q[++tail] = to[i];
}
}
return dep[t] ^ 0x3f3f3f3f;
}
int maxflow;
int dfs(int p,int flow)
{
if(p == t)
return (maxflow += flow,flow);
int ret = 0,used = 0;
for(register int &i = cur[p];~i;i = pre[i])
if(val[i] && dep[to[i]] == dep[p] + 1 && (ret = dfs(to[i],min(flow - used,val[i]))))
{
used += ret,val[i] -= ret,val[i ^ 1] += ret;
if(used >= flow)
break;
}
return used;
}
int dinic()
{
while(bfs())
memcpy(cur,first,sizeof cur),dfs(s,0x3f3f3f3f);
return maxflow;
}
}
int main()
{
freopen("tower.in","r",stdin),freopen("tower.out","w",stdout);
scanf("%d%d",&n,&m),s = 2 * n * m + 1,t = 2 * n * m + 2,Dinic::n = 2 * n * m + 2;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j),Dinic::add(id(i,j,0),id(i,j,1),0x3f3f3f3f);
for(register int i = 1;i <= n;++i)
for(register int j = 1,d,x,y,nx,ny,mx;j <= m;++j)
if(a[i][j] < 0)
{
d = -1 - a[i][j],mx = 0;
for(x = i,y = j;;x = nx,y = ny)
{
nx = x + dx[d],ny = y + dy[d];
if(nx < 1 || nx > n || ny < 1 || ny > m)
break;
mx = max(mx,a[nx][ny]);
}
ans += mx;
if(d < 2)
{
Dinic::add(s,id(i,j,0),mx);
for(x = i,y = j;;x = nx,y = ny)
{
nx = x + dx[d],ny = y + dy[d];
if(nx < 1 || nx > n || ny < 1 || ny > m)
break;
Dinic::add(id(x,y,0),id(nx,ny,0),mx - max(a[x][y],0));
}
}
else
{
Dinic::add(id(i,j,1),t,mx);
for(x = i,y = j;;x = nx,y = ny)
{
nx = x + dx[d],ny = y + dy[d];
if(nx < 1 || nx > n || ny < 1 || ny > m)
break;
Dinic::add(id(nx,ny,1),id(x,y,1),mx - max(a[x][y],0));
}
}
}
ans -= Dinic::dinic();
printf("%d\n",ans);
}