【问题分析】
最大费用最大流问题。
【建模方法】
把网格中每个位置抽象成网络中一个节点，建立附加源S汇T。
1、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为1，费用为该边价值的有向边。
2、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为无穷大，费用为0的有向边。
3、从S到每个出发点i连接一条容量为该点出发的机器人数量，费用为0的有向边。
4、从每个目标点i到T连接一条容量为可以到达该点的机器人数量，费用为0的有向边。
求最大费用最大流，最大费用流值就采集到的生物标本的最高总价值。
【建模分析】
这个问题可以看做是多出发点和目的地的网络运输问题。每条边的价值只能计算一次，容量限制要设为1。同时还将要连接上容量不限，费用为0的重边。由于“多个深海机器人可以在同一时间占据同一位置”，所以不需限制点的流量，直接求费用流即可。
吐槽：这出题人语文tm谁教的，输入看了我老半天
只需要知道权值不在点，而到了边上，而起点和终点变成了多个，起点和终点都有容量限制。
反而使题目变简单了（因为不再有没有权值的边，而且权值在边上比权值在点上多了一个好处——不用拆点）。
——代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 1e9
#define N 1000001
#define min(x, y) ((x) < (y) ? (x) : (y)) int a, b, n, m, cnt, s, t;
int dis[N], pre[N];
int head[N], to[N << ], val[N << ], cost[N << ], next[N << ];
bool vis[N]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline int hash(int x, int y)
{
return x * m + y;
} inline void add2(int x, int y, int z, int c)
{
to[cnt] = y;
val[cnt] = z;
cost[cnt] = c;
next[cnt] = head[x];
head[x] = cnt++;
} inline void add(int x, int y, int z, int c)
{
add2(x, y, z, c);
add2(y, x, , -c);
} inline bool spfa()
{
int i, u, v;
std::queue <int> q;
memset(vis, , sizeof(vis));
memset(pre, -, sizeof(pre));
memset(dis, / , sizeof(dis));
q.push(s);
dis[s] = ;
while(!q.empty())
{
u = q.front(), q.pop();
vis[u] = ;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(val[i] && dis[v] > dis[u] + cost[i])
{
dis[v] = dis[u] + cost[i];
pre[v] = i;
if(!vis[v])
{
q.push(v);
vis[v] = ;
}
}
}
}
return pre[t] ^ -;
} inline int dinic()
{
int i, d, sum = ;
while(spfa())
{
d = INF;
for(i = pre[t]; i ^ -; i = pre[to[i ^ ]]) d = min(d, val[i]);
for(i = pre[t]; i ^ -; i = pre[to[i ^ ]])
{
val[i] -= d;
val[i ^ ] += d;
}
sum += dis[t] * d;
}
return sum;
} int main()
{
int i, j, k, x, y;
a = read();
b = read();
n = read();
m = read();
n++, m++;
s = , t = N - ;
memset(head, -, sizeof(head));
for(i = ; i < n; i++)
for(j = ; j < m; j++)
{
x = read();
add(hash(i, j), hash(i, j + ), , -x);
add(hash(i, j), hash(i, j + ), INF, );
}
for(j = ; j <= m; j++)
for(i = ; i < n - ; i++)
{
x = read();
add(hash(i, j), hash(i + , j), , -x);
add(hash(i, j), hash(i + , j), INF, );
}
while(a--)
{
k = read();
x = read();
y = read();
add(s, hash(x, y + ), k, );
}
while(b--)
{
k = read();
x = read();
y = read();
add(hash(x, y + ), t, k, );
}
printf("%d\n", -dinic());
return ;
}