嘟嘟嘟
这题看数据范围大概能猜出来是网络流，不过作为多年没写网络流的我，建图果然还是没想出来……
首先看到题目说，要想击溃某植物，就必须先击溃某植物，那可能会想到拓扑排序。但是拓扑排序和网络流并没有什么关系，还得换个方法。
然后我就想不到了。正解是我们反着建图，从被保护的植物向保护他的植物连边。于是我们就发现，如果这个点选了，那么他的出边到达的所有点都必须选。而要让选的权值最大，那不就是求最大权闭合子图嘛！
看起来完事了，但其实连样例都过不了，因为图中有环。
所以应该先拓扑排序，进过队列的点就是环外的点，然后只用这些点建的图跑出来才对。
怎么用网络流求最大权闭合子图我就不说了，贴个链接：网络流——最小割求最大权闭合子图
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 25;
const int maxm = 35;
const int maxe = 5e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, s, t;
int val[maxn][maxm], G[maxn * maxm][maxn * maxm];
In int num(int x, int y) {return (x - 1) * m + y;}
int du[maxn * maxm];
bool vis[maxn * maxn];
In void topoSort()
{
queue<int> q;
for(int i = 1; i <= n * m; ++i) if(!du[i]) vis[i] = 1, q.push(i);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = 1; i <= n * m; ++i)
if(G[now][i])
{
if(!--du[i]) vis[i] = 1, q.push(i);
}
}
}
struct Edge
{
int nxt, from, to, cap, flow;
}e[maxe];
int head[maxn * maxm], ecnt = -1;
In void addEdge(int x, int y, int w)
{
e[++ecnt] = (Edge){head[x], x, y, w, 0};
head[x] = ecnt;
e[++ecnt] = (Edge){head[y], y, x, 0, 0};
head[y] = ecnt;
}
int dis[maxn * maxm];
In bool bfs()
{
Mem(dis, 0); dis[s] = 1;
queue<int> q; q.push(s);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if(!dis[v = e[i].to] && e[i].cap > e[i].flow)
{
dis[v] = dis[now] + 1;
q.push(v);
}
}
}
return dis[t];
}
int cur[maxn * maxm];
In int dfs(int now, int res)
{
if(now == t || res == 0) return res;
int flow = 0, f;
for(int& i = cur[now], v; ~i; i = e[i].nxt)
{
if(dis[v = e[i].to] == dis[now] + 1 && (f = dfs(v, min(res, e[i].cap - e[i].flow))) > 0)
{
e[i].flow += f; e[i ^ 1].flow -= f;
flow += f; res -= f;
if(res == 0) break;
}
}
return flow;
}
In int minCut()
{
int flow = 0;
while(bfs())
{
memcpy(cur, head, sizeof(head));
flow += dfs(s, INF);
}
return flow;
}
int sum = 0;
In void buildGraph()
{
for(int i = 1; i <= n; ++i)
for(int j = 1, u; j <= m; ++j)
if(vis[u = num(i, j)])
{
if(val[i][j] > 0) addEdge(s, u, val[i][j]), sum += val[i][j];
else addEdge(u, t, -val[i][j]);
for(int k = 1; k <= n * m; ++k)
if(vis[k] && G[u][k]) addEdge(k, u, INF);
}
}
int main()
{
Mem(head, -1);
n = read(), m = read(); t = num(n, m) + 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
val[i][j] = read();
int w = read(), u = num(i, j);
for(int k = 1, v; k <= w; ++k)
{
int x = read() + 1, y = read() + 1;
G[u][v = num(x, y)] = 1;
++du[v];
}
}
for(int i = 1; i <= n; ++i)
for(int j = 2, x, y; j <= m; ++j)
if(!G[x = num(i, j)][y = num(i, j - 1)]) G[x][y] = 1, ++du[y];
topoSort(); buildGraph();
write(sum - minCut()), enter;
return 0;
}