解题思路
最大权闭合子图。但是要注意一些细节，假如有一堆植物形成一个环，那么这些植物都是无敌的，并且他们保护的植物是无敌的，他们保护的保护的植物是无敌 的。所以要缩点，然后拓扑排序一次判无敌，然后剩下的就是一个最大权闭合子图模板了。源点向正权点连流量为正权的边，负权点向汇点连流量为负权绝对值的边，然后保护关系之间连流量为正无穷的边。最后答案为总正权-最小割。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>using namespace std;
const int MAXN = 605;
const int MAXM = MAXN*MAXN;
const int inf = 0x3f3f3f3f;inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
}int n,m,w[MAXN],head[MAXN],cnt,to[MAXM<<1],nxt[MAXM<<1],val[MAXM<<1];
int S,T,d[MAXN],dfn[MAXN],low[MAXN],col[MAXN],stk[MAXN],top,siz[MAXN];
int tot,col_num,du[MAXN],wt[MAXN],num,cur[MAXN],ans;
bool vis[MAXN],del[MAXN];
queue<int> Q;struct Edge{
int u,v;
}edge[MAXM<<1];inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}inline void addedge(int bg,int ed,int w){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt,val[cnt]=w;
}bool bfs(){
while(Q.size()) Q.pop();
memset(d,0,sizeof(d));d[S]=1;Q.push(S);
while(Q.size()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(!d[u] && val[i]){
d[u]=d[x]+1;
if(u==T) return true;
Q.push(u);
}
}
}
return false;
}int dinic(int x,int flow){
if(x==T) return flow;
int res=flow,k;
for(int &i=cur[x];i && res;i=nxt[i]){
int u=to[i];
if(d[u]==d[x]+1 && val[i]){
k=dinic(u,min(res,val[i]));
if(!k) d[u]=0;
val[i]-=k;val[i^1]+=k;res-=k;
}
}
return flow-res;
}void tarjan(int x){
dfn[x]=low[x]=++tot;vis[x]=1;stk[++top]=x;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(!dfn[u]) tarjan(u),low[x]=min(low[x],low[u]);
else if(vis[u]) low[x]=min(low[x],dfn[u]);
}
if(low[x]==dfn[x]){
vis[x]=0;col[x]=++col_num;wt[col_num]=w[x];
while(stk[top]!=x){
vis[stk[top]]=0;
col[stk[top--]]=col_num;
}top--;
}
}inline void topsort(){
for(int i=1;i<=col_num;i++) if(!du[i]) Q.push(i);
while(Q.size()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=nxt[i]){
int u=to[i];du[u]--;
if(del[x]) del[u]=1;
if(!du[u]) Q.push(u);
}
}
}inline void rebuild(){
memset(head,0,sizeof(head));cnt=1;
for(int i=1;i<=num;i++){
if(del[edge[i].v] || del[edge[i].u]) continue;
addedge(edge[i].v,edge[i].u,inf),addedge(edge[i].u,edge[i].v,0);
}
for(int i=1;i<=col_num;i++)
if(!del[i]){
if(wt[i]>0) addedge(S,i,wt[i]),addedge(i,S,0),ans+=wt[i];
else addedge(i,T,-wt[i]),addedge(T,i,0);
}
}inline void solve(){
while(bfs()) {memcpy(cur,head,sizeof(head));ans-=dinic(S,inf);}
printf("%d\n",ans);
}int main(){
n=rd(),m=rd();S=n*m+1;T=n*m+2;int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
w[(i-1)*m+j]=rd();num=rd();
while(num--){
x=rd()+1,y=rd()+1;
add((i-1)*m+j,(x-1)*m+y);
}
if(j!=1) add((i-1)*m+j,(i-1)*m+j-1);
}
for(int i=1;i<=n*m;i++) if(!dfn[i]) tarjan(i);num=0;
for(int i=1;i<=n*m;i++)
for(int j=head[i];j;j=nxt[j]){
if(col[i]==col[to[j]]) del[col[i]]=1;
else edge[++num].u=col[i],edge[num].v=col[to[j]];
}
memset(head,0,sizeof(head));cnt=0;
for(int i=1;i<=num;i++) {
du[edge[i].v]++;
add(edge[i].u,edge[i].v);
}
topsort();rebuild();solve();
return 0;
}
