结论：这是最大权闭合图的模型
因为可能A保护B，B保护A，出现环。
所以由植物A向植物A保护的植物连边，然后拓扑排序，将环去掉。
然后将拓扑排序的边反向连，建立最大权闭合图的模型。
跑最大流（最小割），用正权边之和-最小割即为答案
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define N 1000001
#define id(i, j) ((i - 1) * m + j)
using namespace std;
int n, m, s, t, T, cnt, sum;
int head[N], to[N], nex[N], val[N], a[N], dis[N], cur[N], d[N];
vector <int> vec[N];
queue <int> q;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
nex[cnt] = head[x];
head[x] = cnt++;
}
inline bool bfs()
{
int i, u, v;
memset(dis, -1, sizeof(dis));
while(!q.empty()) q.pop();
q.push(s);
dis[s] = 0;
while(!q.empty())
{
u = q.front();
q.pop();
for(i = head[u]; ~i; i = nex[i])
{
v = to[i];
if(val[i] && dis[v] == -1)
{
dis[v] = dis[u] + 1;
if(v == t) return 1;
q.push(v);
}
}
}
return 0;
}
inline int dfs(int u, int maxflow)
{
if(u == t) return maxflow;
int v, f, used = 0;
for(int &i = cur[u]; ~i; i = nex[i])
{
v = to[i];
if(val[i] && dis[v] == dis[u] + 1)
{
f = dfs(v, min(val[i], maxflow - used));
used += f;
val[i] -= f;
val[i ^ 1] += f;
if(used == maxflow) return maxflow;
}
}
return used;
}
inline int dinic()
{
int i, ret = 0;
while(bfs())
{
for(i = s; i <= t; i++) cur[i] = head[i];
ret += dfs(s, 1e9);
}
return ret;
}
int main()
{
int i, j, u, v, x, y;
n = read();
m = read();
s = 0, t = n * m + 1;
memset(head, -1, sizeof(head));
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
a[id(i, j)] = read();
if(j > 1)
{
d[id(i, j - 1)]++;
vec[id(i, j)].push_back(id(i, j - 1));
}
T = read();
while(T--)
{
x = read() + 1;
y = read() + 1;
d[id(x, y)]++;
vec[id(i, j)].push_back(id(x, y));
}
}
for(i = 1; i <= n * m; i++)
if(!d[i]) q.push(i);
while(!q.empty())
{
u = q.front();
q.pop();
for(i = 0; i < vec[u].size(); i++)
if(!(--d[vec[u][i]])) q.push(vec[u][i]);
}
for(u = 1; u <= n * m; u++)
if(!d[u])
{
if(a[u] > 0) add(s, u, a[u]), add(u, s, 0), sum += a[u];
if(a[u] < 0) add(u, t, -a[u]), add(t, u, 0);
for(i = 0; i < vec[u].size(); i++)
{
v = vec[u][i];
if(!d[v]) add(v, u, 1e9), add(u, v, 0);
}
}
printf("%d
", sum - dinic());
return 0;
}